__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!