Often known as Fermat's theorem, which runs the risk of confusing it with Wiles' theorem. This little fact from number theory was proved by Fermat.

Theorem. Let p be a prime number, and let a be any integer. Then a^p = a (modulo p).

Like the similar Wilson's theorem, the proof of Fermat's little theorem is not too difficult, but a bit hard to grasp at first. The proof originally on the linked node used algebra, and was very different from the proof below, which uses combinatorics. It's based on multiplying the fact that the integers modulo p are a (finite) field. Unfortunately there's an editorial decision to avoid proofs on separate nodes from their theorems. As I believe the proof doesn't belong here (it has nothing to do with how the theorem is applied, which is the usual motive for linking over here), I cannot paste it below. You should be able to reconstruct the proof from the description above; if desperate, /msg me and I'll answer privately.

As an example, take p=5 and a=4. Then 4⁵ = 1024 is clearly 4 modulo 5 (it ends with a 4 or 9 digit).

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!