### Statement:

- Let
*p* be a prime then *a*^{p} ≡ a (mod *p*), for any natural number *a*.

### Proof using Modular Arithmetic:

Firstly, we need to discuss Wilson’s theorem. This states:

(p-1)! ≡ -1 (mod *p*) is *p* is prime.

We must first prove this theorem:

If *p* is prime, then 1, 2, …, p-1 are invertible mod *p*. Now we can pair each of these numbers with its inverse (for example 3 with 4 in mod 11). The only elements that cannot be paired with a different number are 1 and -1, which are self-inverses, as shown below:

Now (p-1)! is a product of (p-3)/2 inverse pairs together with -1 and 1, whose product is **-1**.

So **(p-1)! ≡ -1 (mod ***p*).

Back to the proof of Fermat’s Little Theorem.

The statement of Fermat’s Little Theorem is equivalent to *a*^{p-1 }≡ 1 (mod *p*) if a ≢ 0 (mod *p*).

Consider the numbers a, 2a, …., (p-1)a. These are each distinct mod *p* and so they are congruent to 1, 2, …., (p-1) (mod *p*) in some order.

Hence a·2a···(p-1)a ≡ 1·2···(p-1) (mod *p*).

So *a*^{p-1}(p-1)! ≡ (p-1)!.

And therefore *a*^{p-1 }≡ 1 (mod *p*).

We can extend this to *a*^{p }≡ a (mod *p*) as shown below:

**When a ≡ 0 (mod ***p*): 0^{p }≡ 0 (mod *p*). So *a*^{p }≡ a (mod *p*).

**When a ≢ 0 (mod ***p*): We can multiply through by *a*, as *a* and *p* are coprime. Then we get *a*^{p }≡ a (mod *p*), as required.

Hence, we have proved Fermat’s Little Theorem, a very important result in number theory.

M x