Fermat's Little Theorem
1. Introduction
if p is a prime number, then for any integer a, the number ap − a is an integer multiple of p. In the notation of modular arithmetic, this is expressed as:
a p ≡ a (mod p)
If a is not divisible by p, Fermat's little theorem is equivalent to the statement that a p−1−1 is an integer multiple of p, or in symbols:
a p-1 ≡ 1 (mod p)
2. Proof
Step 1. Suppose that a is not divisible by the prime p, no two of the integers 1*a , 2*a , . . . , (p-1)*a are congruent modulo p.
- Suppose 2 integer s*a and r*a (both 0 < s and r < p) are congruent modulo p, s*a ≡ r*a (mod p).
- Since a ≡ 1(mod p), therefore s ≡ r (mod p).
- Since 0 < s and r < p, s = r.
- This suggests that no tow of integers 1*a , 2*a , . . . , (p-1)*a are congruent modulo p.
Step 2. From step 1, we can prove that:
(p-1) ! ≡ ap-1* (p-1) ! (mod p)
Since step 1 shows that no two of the integers 1*a , 2*a , . . . , (p-1)*a are congruent modulo p, we conclude that, 1*a mod p, 2*a mod p, .... (p-1)*a mod p, must be different number from 1 to p-1.
Therefore, (1*a) * (2*a) * ... * ((p-1)*a) mod p = 1*2*...*(p-1) = (p-1)! ≡ (p-1)! mod p.
Simplify it, we get: ap-1 * (p-1)! ≡ (p-1)! (mod p)
Step 3. show that ap-1 ≡ 1 (mod p) if p does not divide a .
Since p is a prime, there is no factor for p from 2 to p-1, therefor gcd(p, (p-1)!) = 1, and we can simplify ap-1 * (p-1)! ≡ (p-1)! (mod p)
and get: ap-1 ≡ 1 (mod p)
Step 4. show that a p ≡ a (mod p) for all integers a .
Since gcd(p, a) = 1, ap-1 ≡ 1 (mod p)
a*ap-1 ≡ a*1 (mod p) => ap ≡ a (mod p)
