7.2 CONGRUENCE 231We are not going to prove this; Fermat's Last Theorem was perhaps the most
famous outstanding problem in all of mathematics. The French mathematician Fermat
conjectured its truth over 300 years ago, and the problem remained unsolved until
19 95. But we shall point out two simplifications.
• Without loss of generality, n is prime. For example, if..J + y^3 = z^3 has no non
zero integer solutions, the same will be true of x^12 + y^12 = z^12 , since this latter
equation can be rewritten as- Likewise, we may assume that x, y, z is a primitive solution; i.e., x, y, z have
no common factor (other than 1). To see why, suppose that g is the greatest
common divisor of x,y,z. Then x = ga,y = gb,z = gc for some integers a, b, c.
Notice that a, b, c have no common factor, and
:x!' + yn = zn {:::=} (ga)n + (gb t = (gc t {:::=} an + bn = cn,
where the third equality followed from the second after division by gn.
What's So Good About Primes?
One reason that primes are so convenient is that unique "multiplicative inverses" exist.
For example, in Z6, the number 5 has a multiplicative inverse, namely itself, since
5·5= 1 (mod 6). However, 2 has no multiplicative inverse, nor does 4. In contrast,
all the non-zero elements of Z7 have inverses, and they are unique. We have
1·1 = 2·4 = 3·5 = 6·6 = 1 (mod 7),so the inverses of 1,2,3,4,5,6 in Z7 are respectively 1,4,5,2,3,6. In general,
If p is prime, and x is not a multiple of p, then there is a unique y E
{1,2,3, ... ,p-1}such thatxy= 1 (modp).
This was proven in Example 2.3. 4 on page 44. The penultimate step was the very
useful fact that
If p is prime, and x =1- 0 (mod p), then the (p -1) numbers
x,2x,3x, ... , (p -1)x
are distinct in Zp.
Equivalently, if p is prime, and x =1- 0 (mod p), then in Zp,
{x,2x,3x, ... ,(p - 1 )x} = {1,2,3, ... ,p- (^1) }.
For example, if p = 7 and x = 4, then we have (mod p)
4·1=4 , 4·2=1, 4·3=5, 4·4=2, 4·5=6, 4·6=3,(1)verifying that the set of the non-zero mUltiples of 4 in Z7 is just a permutation of the
non-zero values of Z7.