The Little Theorem of Pierre de Fermat (1601‐1665) states that if p is prime and a is a positive integer that is not a multiple of p then

a^{p−1} ≡ 1 (mod p)

Proof: We will use modular arithmetic. As a refresher, remember that if b_{1} ≡ c_{1} (mod m) and b_{2} ≡ c_{2} (mod m) then b_{1} + b_{2} ≡ c_{1} + c_{2} (mod m) and b_{1}b_{2} ≡ c_{1}c_{2} (mod m). Furthermore, if bc ≡ bd (mod m) and b is relatively prime to m, then c ≡ d (mod m).

Consider the sequences S_{1} = 1, 2, 3, ..., p−1 and S_{2} = a, 2a, 3a, ..., (p−1)a, where a is any positive integer. We will show that, when reduced modulo p, each member of S_{2} corresponds to one and only one member of S_{1}. That is, {1, 2, 3, ..., p−1} = {a, 2a, 3a, ..., (p−1)a}, where all elements in the latter set are reduced modulo p.

By contradiction, let the integers i and j be such that 0 ≤ i < p and 0 ≤ j < p with i ≠ j. Let ia ≡ ja (mod p).

That is, p | ia − ja, which in turn means that ∃w ≥ 1: wp = a(i−j). So p = (a/w)(i−j). But since p is prime, then either (1) a/w = 1 and i − j = p or (2) a/w = p and i − j = 1.

If (1) is true, then p = i − j. But p > i. This implies that i − j > i, or j < 0, a contradiction.

If (2) is true, then a = wp. But a < p. So we have wp < p or w < 1, a contradiction.

We have established that i = j, and all distinct elements of S_{2} when reduced modulo p correspond to distinct elements of S_{1}.

Next, using p−1 applications of modular multiplication, we assert that the product of all of the elements of S_{1} is equal to the product of all of the elements of S_{2}, modulo p.

∏_{n=1}^{p−1}na ≡ ∏_{n=1}^{p−1}n (mod p)

a^{p−1}(p−1)! ≡ (p−1)! (mod p)

For the last step, we use the result from number theory that says that an integer k has a multiplicative inverse modulo m if and only if gcd(k, m) = 1.

Consider gcd[(p−1)!, p]. p is prime and so the only factor it has in common with (p−1)! is 1. So (p−1)! has a multiplicative inverse, and we may "divide" both sides of the modular equivalence above by it. We have

a^{p−1} ≡ 1 (mod p)

QED

Source: wikipedia.org