Fermat theorem: (a.k.a. "Little Fermat Theorem")
[ i ]
If
p is a
prime and
a is an
integer,
then
a p ≡
a mod p.
[ ii ]
If
p is a
prime,
a is an integer, and k is a positive integer,
then
a pk ≡
a mod
p.
Proof: (
LEIBNIZ)
Induction on
nonnegative a.
basis step: a = 0.
0 p ≡ 0 mod p.
Induction step:
(1) (a + 1) p
≡ a p + 1 p mod p
(2) (a + 1) p
≡ a + 1 mod p
(1) holds because the binomial coefficient for each term in the binomial expansion of (x + y) p,
p choose r, for 0 < r < p is divisible by p.* Hence the first and last terms of the expansion remains.
In equation (2), a p is congruent to a by the induction hypothesis.
For negative
a and odd
p, The negative sign factors out and cancels each other.
For negative
a and
p = 2, the theorem holds because an
even squared is always even, and an odd squared is always
odd.
[ ii ]
is easily proven by
induction on
k.
QED
* p is a
divisor of (p
choose r) may need a little more explanation:
(p choose r) = p ! / ( r ! ( p - r ) ! )
(p choose r) = p ( p - 1 )...( p - r + 1 ) / r
!
r! (p choose r) = p ( p - 1)...( p - r + 1 )
p divides the right side, so p must also divide the left side.
Since p's factors are p and 1, and r is less than p,
p does not divide r
factorial, and so by
Euclid's First Theorem, p divides (p choose r).
hooray!