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
ap−1 ≡ 1 (mod p)
Proof: We will use modular arithmetic. As a refresher, remember that if b1 ≡ c1 (mod m) and b2 ≡ c2 (mod m) then b1 + b2 ≡ c1 + c2 (mod m) and b1b2 ≡ c1c2 (mod m). Furthermore, if bc ≡ bd (mod m) and b is relatively prime to m, then c ≡ d (mod m).
Consider the sequences S1 = 1, 2, 3, ..., p−1 and S2 = a, 2a, 3a, ..., (p−1)a, where a is any positive integer. We will show that, when reduced modulo p, each member of S2 corresponds to one and only one member of S1. 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 S2 when reduced modulo p correspond to distinct elements of S1.
Next, using p−1 applications of modular multiplication, we assert that the product of all of the elements of S1 is equal to the product of all of the elements of S2, modulo p.
∏n=1p−1na ≡ ∏n=1p−1n (mod p)
ap−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
ap−1 ≡ 1 (mod p)
QED
Source: wikipedia.org