This exercise outlines a proof of Fermat's little theorem.
a) Suppose that a is not divisible by the prime p. Show that no two of the integers 1 · a, 2 · a, . . . , (p − 1)a are congruent modulo p.
b) Conclude from part (a) that the product of 1, 2, . . . , p − 1 is congruent modulo p to the product of a, 2a, . . . , (p − 1)a. Use this to show that
(p − 1)! ≡ ap−1(p − 1)! (mod p).
c) Use Theorem 7 of Section 4.3 to show from part (b) that ap−1 ≡ 1 (mod p) if p X a.
d) Use part (c) to show that ap ≡ a (mod p) for all integers a.