### 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) ispis 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