3.1 SYMMETRY 69multiplicative inverse modulo p; i.e., if x is not a mUltiple of p then there is a unique
y E {I, 2, 3, ... ,p - I} such that xy = 1 (mod p). (Recall the proof of this assertion in
Example 2.3.4 on page 44.)
Armed with this information, we proceed as in the locker problem: Pair eachelement x E {I, 2, 3, ... ,p - I} with its "natural" mate y E {I, 2, 3, ... ,p - I} such that
xy = 1 (mod p). For example, if p = 13, the pairs are
( 1 , 1), (2, 7), (3,9), (4, 10), (5,8), (6, 11), (12, 12),
and we can rewrite
12! = 1 · 2 ·3·4· 5·6·7· 8 · 9 · 10 · 11 · 12
as
1 · (2·7)(3·9)(4 ·10)(5· 8)(6·11) ·12=1 · 1 · 1·1·1·1·12=- 1 (mod 13).
Notice that 1 and 12 were the only elements that paired with themselves. Notice also
that 12 = -1 (mod 13). We will be done in general if we can show that x is its own
multiplicative inverse modulo p if and only if x = ± 1. But this is easy: If J? = 1
(mod p), thenx^2 - 1 = (x -l)(x+ 1) =^0 (mod p).
Because p is prime, this implies that either x-I or x + 1 is a multiple of p; i.e., x = ± 1
(mod p) are the only possibilities. _
Symmetry in Polynomials and Inequalities
Algebra problems with many variables or of high degree are often intractable unless
there is some underlying symmetry to exploit. Here is a lovely example.
Example 3.1.10 Solve x^4 +.J + J? + x + 1 = o.
Solution: While there are other ways of approaching this problem (see page 126),
we will use the symmetry of the coefficients as a starting point to impose yet more
symmetry, on the degrees of the terms. Simply divide by J? :
1 1
x^2 +x+l+-+z=0.
x x
This looks no simpler, but note that now there is more symmetry, for we can collect
"like" terms as follows: