Let $p \in \Z$ and a prime number and $a \in \Z$ such that $\mathrm{gcd}(a,p) = 1$ then $a^{p-1} \equiv 1 \pmod{p}$. Furthermore for all $a \in \Z$, we have $a^p \equiv a \pmod{p}$

Proof

We are calculating in $\Z_p$.

First let us show that $1\cdot a, 2 \cdot a, 3 \cdot a, ..., (p-1) \cdot a$ are all different $\pmod{p}$.

Let $r$ and $s$ be such that $r\cdot a \equiv s\cdot a \pmod{p}$. Since gcd$(a,p) = 1$, then $r \equiv s \pmod{p}$ by a preceding lemma.

Since they are all different, then $1\cdot a, 2 \cdot a, 3 \cdot a, ..., (p-1) \cdot a$ is a permutation of non-zero elements of $\Z_p$

$(1\cdot a) (2 \cdot a) (3 \cdot a) ... ((p-1) \cdot a) \equiv 1\cdot 2 \cdot 3 \cdot ... \cdot (p-1)$
$1\cdot 2 \cdot 3 \cdot ... \cdot (p-1) \cdot a^{p-1} \equiv 1\cdot 2 \cdot 3 \cdot ... \cdot (p-1)$

$2 < p$ and $p$ is prime, so gcd$(2,p) = 1$
$3 < p$ and $p$ is prime, so gcd$(3,p) = 1$
...
$p-1 < p$ and $p$ is prime, so gcd$(p-1,p) = 1$

It follows that:

$a^{p-1} = 1 \pmod{p}$

For the second statement we consider two cases:

1. if gcd$(a,p)= 1$

   then we just show that
   $a^{p-1} = 1 \pmod{p}$
   $a^{p} = a \pmod{p}$

2. if gcd$(a,p)\neq 1$

   then gcd$(a,p) = p$
   therefore $a \equiv 0 \equiv 0^p \equiv a^p \pmod{p}$

Pseudo-primes

If $p$ is an odd prime, then $2^{p-1} \equiv 1 \pmod{p}$

If $n$ is composite and $b^{n-1} \equiv 1 \pmod{m}$ we say that $n$ is pseudo-prime base b.