88 CHAPTER 2 Discrete Mathematics
- Let p be a prime number. The integers a and b are said to be
multiplicative inverses modulopifab≡1(modp). Using the
Euclidean trick, prove that if p doesn’t divide a, then a has a
multiplicative inverse modulop. - Find the multiplicative inverse of 2 modulo 29.
- Find the multiplicative inverse of 3 modulo 113.
- Prove Wilson’s Theorem:
(p−1)!≡−1(modp),
where p is a prime. (Hint; pair each divisor of (p−1)! with its
inverse modulop; of course, this requires the result of exercise 4,
above.) - Theorderof the integeramodulo the primepis theleastpositive
integer n such thatan ≡ 1(modp). Show that n|p−1. (Hint:
show that ifd= gcd(n,p−1), thenad≡1(mod p).) - As we saw from Fermat’s little theorem, if p is prime and if a
is an integer not divisible by p, then ap−^1 ≡ 1 (modp). What
about the converse? That is, suppose that nis a positive integer
and that for every integerarelatively prime ton we havean−^1 ≡
1 (modn). Mustnthen be prime? Looking for a counter example
takes some time, leading one to (almost) believe this converse.
However, suppose that we were to find a candidate integernand
found that for every prime divisorp of n, that p− 1 |n−1.
Show thatnsatisfies the above.^18 - Here’s a very surprising application of Euler’s Theorem, above.^19
Define the sequence a 1 , a 2 , ..., by settinga 1 = 2, a 2 = 2a^1 , a 3 =
2 a^2 , .... Then for any integern, the sequence a 1 , a 2 , ..., even-
tually becomes constant (modn). The proof proof proceeds by
induction onnand can be carried out along the following lines.
(^18) Such an integer is called aCarmichael number, the first such beingn= 561, which is why
the converse to Fermat’s little theorem can appear true! It is known that there are, in fact, infinitely
many Carmichael numbers, which means that there are infinitely many counter examples to the
converse of Fermat’s little theorem. 19
I’m indebted to my student, Nelson Zhang, for pointing out this exercise, commenting also that
this is Problem #3 on the 1991 USA Olympiad contest. The hints given above are the result of our
discussion.