This exercise outlines a proof of Fermat's little

Chapter 4, Problem 19E

(choose chapter or problem)

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 \cdot a, 2 \cdot a, \ldots,(p-1) a\) are congruent modulo \(p\).

b) Conclude from part (a) that the product of \(1,2, \ldots, p-1\) is congruent modulo \(p\) to the product of \(a, 2 a, \ldots,(p-1) a\). Use this to show that

(p-1) ! \equiv a^{p-1}(p-1) !(\bmod p) .

c) Use Theorem 7 of Section 4.3 to show from part (b) that \(a^{p-1} \equiv 1(\bmod p)\) if \(p \times a\). [Hint: Use Lemma 3 of Section 4.3 to show that \(p\) does not divide \((p-1)\) ! and then use Theorem 7 of Section 4.3. Alternatively, use Wilson's theorem from Exercise 18(b).]

d) Use part (c) to show that \(a^{p} \equiv a(\bmod p)\) for all integers \(a\).

Equation Transcription:

Text Transcription:

a

p

1 \cdot a, 2 \cdot a, \ldots,(p-1) a

p

1,2, \ldots, p-1

p

a, 2 a, \ldots,(p-1) a

(p-1) ! \equiv a^{p-1}(p-1) !(\bmod p) .

a^{p-1} \equiv 1(\bmod p)

p X a

 p

(p-1) !

a^{p} \equiv a(\bmod p)

a