# Proof of Fermat's Little Theorem

1. Sep 8, 2005

### 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).

2. Sep 8, 2005

### 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).

3. Sep 8, 2005

### amcavoy

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: Sep 8, 2005
4. Sep 8, 2005

### 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.

5. Sep 9, 2005

### matt grime

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

6. Sep 10, 2005

### amcavoy

Yes, right. I have it now thanks.