Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof of Fermat's Little Theorem

  1. Sep 8, 2005 #1
    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.
  2. jcsd
  3. Sep 8, 2005 #2
    (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.


    (1a)(2a)...((p - 1)a) = 1*2*...*(p - 1) (mod p)
    (p - 1)! * a^(p - 1) = (p - 1)! (mod p).
  4. Sep 8, 2005 #3
    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
  5. Sep 8, 2005 #4
    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.
  6. Sep 9, 2005 #5

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    if it were mod a then the RHS would be identically zero, wouldn't it?
  7. Sep 10, 2005 #6
    Yes, right. I have it now thanks.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook