Introduction to Cryptography with Coding Theory, 3rd Edition

3.6 Fermat’s Theorem and Euler’s Theorem

Two of the most basic results in number theory are Fermat’s and Euler’s theorems. Originally admired for their theoretical value, they have more recently proved to have important cryptographic applications and will be used repeatedly throughout this book.

Fermat’s Theorem

If $p$ is a prime and $p$ does not divide $a\text{,}$ then

$$\begin{array}{cc}{a}^{p-1}\equiv 1& (\text{mod}p)\text{.}\end{array}$$

Proof. Let

$$S=\{1\text{,}2\text{,}3\text{,}\dots \text{,}p-1\}\text{.}$$

Consider the map $\psi :S\to S$ defined by $\psi (x)=ax(\text{mod}p)\text{.}$ For example, when $p=7$ and $a=2\text{,}$ the map $\psi$ takes a number $x\text{,}$ multiplies it by 2, then reduces the result mod 7.

We need to check that if $x\in S\text{,}$ then $\psi (x)$ is actually in $S\text{;}$ that is, $\psi (x)\ne 0\text{.}$ Suppose $\psi (x)=0\text{.}$ Then $ax\equiv 0(\text{mod}p)\text{.}$ Since $gcd(a\text{,}p)=1\text{,}$ we can divide this congruence by $a$ to obtain $x$