Proof of Fermat's Little Theorem

In summary, the proof of Fermat's little theorem involves considering p-1 distinct numbers that are congruent to 1, 2, ..., p-1 mod p. Since a is invertible mod p, these numbers must be distinct and can be written as (1a)(2a)...((p-1)a). This is equivalent to (p-1)! * a^(p-1) = (p-1)! (mod p). If we were to use mod a instead of mod p, the RHS would be zero and the proof would not hold. This explanation can also be found in online resources about number theory.
  • #1
amcavoy
665
0
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.
 
Physics news on Phys.org
  • #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.

Thus

(1a)(2a)...((p - 1)a) = 1*2*...*(p - 1) (mod p)
<=>
(p - 1)! * a^(p - 1) = (p - 1)! (mod p).
 
  • #3
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:
  • #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.
 
  • #5
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?
 
  • #6
Yes, right. I have it now thanks.
 

What is "Proof of Fermat's Little Theorem"?

"Proof of Fermat's Little Theorem" is a mathematical proof that was first stated by French mathematician Pierre de Fermat in 1640. It states that for any prime number p and any integer a, ap will always be congruent to a modulo p.

Why is "Proof of Fermat's Little Theorem" important?

"Proof of Fermat's Little Theorem" is important because it has many applications in number theory and cryptography. It is also a fundamental theorem in algebra that helps to understand the properties of prime numbers.

What is the significance of Fermat's Little Theorem in cryptography?

Fermat's Little Theorem is used in cryptography to generate strong pseudorandom numbers, which are essential for ensuring the security of encryption algorithms. It is also used in the RSA algorithm, which is widely used in secure communication over the internet.

What is a congruence modulo p?

A congruence modulo p means that two numbers have the same remainder when divided by p. In other words, if a and b are two integers and p is a prime number, then a is congruent to b modulo p if and only if a mod p = b mod p.

How is Fermat's Little Theorem proven?

The proof of Fermat's Little Theorem involves using mathematical induction and the binomial theorem. It can also be proven using group theory and Euler's theorem. The complete proof was provided by Leonhard Euler in 1736.

Similar threads

  • Linear and Abstract Algebra
Replies
17
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
887
  • Linear and Abstract Algebra
Replies
11
Views
1K
  • Precalculus Mathematics Homework Help
Replies
6
Views
820
  • Linear and Abstract Algebra
Replies
2
Views
493
  • Precalculus Mathematics Homework Help
Replies
1
Views
971
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
Replies
4
Views
602
  • Linear and Abstract Algebra
Replies
3
Views
963
  • Linear and Abstract Algebra
Replies
12
Views
1K
Back
Top