Proof of Fermat's Little Theorem

  • Thread starter amcavoy
  • Start date
663
0

Main Question or Discussion Point

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

Thanks for your help.
 

Answers and Replies

694
0
(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).
 
663
0
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:
1,056
0
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
Science Advisor
Homework Helper
9,394
3
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?
 
663
0
Yes, right. I have it now thanks.
 

Related Threads for: Proof of Fermat's Little Theorem

  • Last Post
Replies
7
Views
6K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
4
Views
2K
Replies
1
Views
2K
Replies
3
Views
981
Replies
1
Views
2K
  • Last Post
Replies
1
Views
3K
Replies
3
Views
2K
Top