- Let p be a prime then ap ≡ a (mod p), for any natural number a.
Proof using Modular Arithmetic:
Firstly, we need to discuss Wilson’s theorem. This states:
(p-1)! ≡ -1 (mod p) is p is prime.
We must first prove this theorem:
If p is prime, then 1, 2, …, p-1 are invertible mod p. Now we can pair each of these numbers with its inverse (for example 3 with 4 in mod 11). The only elements that cannot be paired with a different number are 1 and -1, which are self-inverses, as shown below:
Now (p-1)! is a product of (p-3)/2 inverse pairs together with -1 and 1, whose product is -1.
So (p-1)! ≡ -1 (mod p).
Back to the proof of Fermat’s Little Theorem.
The statement of Fermat’s Little Theorem is equivalent to ap-1 ≡ 1 (mod p) if a ≢ 0 (mod p).
Consider the numbers a, 2a, …., (p-1)a. These are each distinct mod p and so they are congruent to 1, 2, …., (p-1) (mod p) in some order.
Hence a·2a···(p-1)a ≡ 1·2···(p-1) (mod p).
So ap-1(p-1)! ≡ (p-1)!.
And therefore ap-1 ≡ 1 (mod p).
We can extend this to ap ≡ a (mod p) as shown below:
When a ≡ 0 (mod p): 0p ≡ 0 (mod p). So ap ≡ a (mod p).
When a ≢ 0 (mod p): We can multiply through by a, as a and p are coprime. Then we get ap ≡ a (mod p), as required.
Hence, we have proved Fermat’s Little Theorem, a very important result in number theory.