Fermat theorem:  (a.k.a. "Little Fermat Theorem")
[ i ] If p is a prime and a is an integer, then a pa mod p.  [ ii ] If p is a prime, a is an integer, and k is a positive integer, then a pka mod p.

Proof: (LEIBNIZ)
Induction on nonnegative a.
basis step: a = 0.
0 p ≡ 0 mod p.

Induction step:
(1)   (a + 1) pa p + 1 p mod p
(2)   (a + 1) pa + 1 mod p

(1) holds because the binomial coefficient for each term in the binomial expansion of (x + y) pp 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.
* 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!