Proof of Fermat's Little Theorem

  • Thread starter Thread starter amcavoy
  • Start date Start date
  • Tags Tags
    Proof Theorem
amcavoy
Messages
663
Reaction score
0
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.
 
Physics news on Phys.org
(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).
 
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.
 
Last edited:
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.
 
apmcavoy said:
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?
 
Yes, right. I have it now thanks.
 
Back
Top