Proof of Fermat's Little Theorem

[amcavoy]

I just have one question about the proof. Why does (p-1)!a^{p-1}=(p-1)!\pmod{p}? It seems like it would be true if the (mod p) was instead (mod a).

Thanks for your help.

 

[Muzza]

(There is more than one proof of Fermat's little theorem.)

Let a be invertible mod p.

Consider the p - 1 numbers

1a, 2a, ..., (p - 1)a.

Since a was invertible, they are all distinct mod p. So we have p - 1 numbers which are distinct mod p, so they must be congruent to 1, 2, 3, ..., p - 1 in some order.

Thus

(1a)(2a)...((p - 1)a) = 1*2*...*(p - 1) (mod p)
<=>
(p - 1)! * a^(p - 1) = (p - 1)! (mod p).

 

[amcavoy]

Since a was invertible, they are all distinct mod p. So we have p - 1 numbers which are distinct mod p, so they must be congruent to 1, 2, 3, ..., p - 1 in some order.

Can you explain this? I understand the rest of the proof except for this part.

Thanks again.

While I'm at it: I have asked this before, but received responses with suggestions for books to read. Is there any good online material to read about number theory? Anything would be good, but I don't want to spend a lot of money on books and my local library has nothing on number theory.

 

[robert Ihnot]

What he is saying above is that each one of ja is unique. Since if ja==ka Mod p, then multiplying by a^-1, we have ja(a^-1)==ka(a^-1) Mod p implies j==k Mod p.

 

[matt grime]

It seems like it would be true if the (mod p) was instead (mod a).

if it were mod a then the RHS would be identically zero, wouldn't it?

 

[amcavoy]

Yes, right. I have it now thanks.