# 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{,}\text{}$ then

Proof. Let

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

We need to check that if $x\in S\text{,}\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{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}p)\text{.}$ Since $gcd(a\text{,}\text{}p)=1\text{,}\text{}$ we can divide this congruence by $a$ to obtain $x\equiv 0\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}p)\text{,}\text{}$ so $x\text{\hspace{0.17em}}\overline{)\in}\text{\hspace{0.17em}}S\text{.}$ This contradiction means that $\psi (x)$ cannot be 0, hence $\psi (x)\in S\text{.}$ Now suppose there are $x\text{,}\text{}y\in S$ with $\psi (x)=\psi (y)\text{.}$ This means $ax\equiv ay\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}p)\text{.}$ Since $gcd(a\text{,}\text{}p)=1\text{,}\text{}$ we can divide this congruence by $a$ to obtain $x\equiv y\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}p)\text{.}$ We conclude that if $x\text{,}\text{}y$ are distinct elements of $S\text{,}\text{}$ then $\psi (x)$ and $\psi (y)$ are distinct. Therefore,

are distinct elements of $S\text{.}$ Since $S$ has only $p-1$ elements, these must be the elements of $S$ written in a some order. It follows that

Since $gcd(j\text{,}\text{}p)=1$ for $j\in S\text{,}\text{}$ we can divide this congruence by $1\text{,}\text{}2\text{,}\text{}3\text{,}\text{}\text{\hspace{0.17em}}\dots \text{\hspace{0.17em}}\text{,}\text{}p-1\text{.}$ What remains is $1\equiv {a}^{p-1}\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}p)\text{.}$

# Example

${2}^{10}=1024\equiv 1\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}11)\text{.}$ From this we can evaluate ${2}^{53}\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}11)\text{:}$ Write ${2}^{53}=({2}^{10}{)}^{5}{2}^{3}\equiv {1}^{5}{2}^{3}\equiv 8\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}11)\text{.}$ Note that when working mod 11, we are essentially working with the exponents mod 10, not mod 11. In other words, from $53\equiv 3\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}10)\text{,}\text{}$ we deduce ${2}^{53}\equiv {2}^{3}\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}11)\text{.}$

The example leads us to a very important fact:

# Basic Principle

Let $p$ be prime and let $a\text{,}\text{}x\text{,}\text{}y$ be integers with $gcd(a\text{,}\text{}p)=1\text{.}$ If $x\equiv y\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}p-1)\text{,}\text{}$ then ${a}^{x}\equiv {a}^{y}\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}p)\text{.}$ In other words, if you want to work mod $p\text{,}\text{}$ you should work mod $p-1$ in the exponent.

Proof. Write $x=y+(p-1)k\text{.}$ Then

This completes the proof.

In the rest of this book, almost every time you see a congruence mod $p-1\text{,}\text{}$ it will involve numbers that appear in exponents. The Basic Principle that was just stated shows that this translates into an overall congruence mod $p\text{.}$ Do not make the (unfortunately, very common) mistake of working mod $p$ in the exponent with the hope that it will yield an overall congruence mod $p\text{.}$ It doesn’t.

We can often use Fermat’s theorem to show that a number is composite, without factoring. For example, let’s show that 49 is composite. We use the technique of Section 3.5 to calculate

Since

we conclude that 49 cannot be prime (otherwise, Fermat’s theorem would require that ${2}^{48}\equiv 1\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}49)$). Note that we showed that a factorization must exist, even though we didn’t find the factors.

Usually, if ${2}^{n-1}\equiv 1\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}n)\text{,}\text{}$ the number $n$ is prime. However, there are exceptions: $561=3\cdot 11\cdot 17$ is composite but ${2}^{560}\equiv 1\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}561)\text{.}$ We can see this as follows: Since $560\equiv 0\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}2)\text{,}\text{}$ we have ${2}^{560}\equiv {2}^{0}\equiv 1\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}3)\text{.}$ Similarly, since $560\equiv 0\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}10)$ and $560\equiv 0\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}16)\text{,}\text{}$ we can conclude that ${2}^{560}\equiv 1\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}11)$ and ${2}^{560}\equiv 1\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}17)\text{.}$ Putting things together via the Chinese remainder theorem, we find that ${2}^{560}\equiv 1\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}561)\text{.}$

Another such exception is $1729=7\cdot 13\cdot 19\text{.}$ However, these exceptions are fairly rare in practice. Therefore, if ${2}^{n-1}\equiv 1\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}n)\text{,}\text{}$ it is quite likely that $n$ is prime. Of course, if ${2}^{n-1}\text{\hspace{0.17em}}\overline{)\equiv}\text{\hspace{0.17em}}1\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}n)\text{,}\text{}$ then $n$ cannot be prime.

Since ${2}^{n-1}\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}n)$ can be evaluated very quickly (see Section 3.5), this gives a way to search for prime numbers. Namely, choose a starting point ${n}_{0}$ and successively test each odd number $n\ge {n}_{0}$ to see whether ${2}^{n-1}\equiv 1\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}n)\text{.}$ If $n$ fails the test, discard it and proceed to the next $n\text{.}$ When an $n$ passes the test, use more sophisticated techniques (see Section 9.3) to test $n$ for primality. The advantage is that this procedure is much faster than trying to factor each $n\text{,}\text{}$ especially since it eliminates many $n$ quickly. Of course, there are ways to speed up the search, for example, by first eliminating any $n$ that has small prime factors.

For example, suppose we want to find a random 300-digit prime. Choose a random 300-digit odd integer ${n}_{0}$ as a starting point. Successively, for each odd integer $n\ge {n}_{0}\text{,}\text{}$ compute ${2}^{n-1}\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}n)$ by the modular exponentiation technique of Section 3.5. If ${2}^{n-1}\text{\hspace{0.17em}}\overline{)\equiv}\text{\hspace{0.17em}}1\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}n)\text{,}\text{}$ Fermat’s theorem guarantees that $n$ is not prime. This will probably throw out all the composites encountered. When you find an $n$ with ${2}^{n-1}\equiv 1\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}n)\text{,}\text{}$ you probably have a prime number. But how many $n$ do we have to examine before finding the prime? The Prime Number Theorem (see Subsection 3.1.2) says that the number of 300-digit primes is approximately $1.4\times {10}^{297}\text{,}\text{}$ so approximately 1 out of every 690 numbers is prime. But we are looking only at odd numbers, so we expect to find a prime approximately every 345 steps. Since the modular exponentiations can be done quickly, the whole process takes much less than a second on a laptop computer.

We’ll also need the analog of Fermat’s theorem for a composite modulus $n\text{.}$ Let $\varphi (n)$ be the number of integers $1\le a\le n$ such that $gcd(a\text{,}\text{}n)=1\text{.}$ For example, if $n=10\text{,}\text{}$ then there are four such integers, namely 1,3,7,9. Therefore, $\varphi (10)=4\text{.}$ Often $\varphi $ is called **Euler’s $\varphi $-function**.

If $p$ is a prime and $n={p}^{r}\text{,}\text{}$ then we must remove every $p$th number in order to get the list of $a$’s with $gcd(a\text{,}\text{}n)=1\text{,}\text{}$ which yields

In particular,

More generally, it can be deduced from the Chinese remainder theorem that for any integer $n\text{,}\text{}$

where the product is over the distinct primes $p$ dividing $n\text{.}$ When $n=pq$ is the product of two distinct primes, this yields

# Examples

# Euler’s Theorem

If $gcd(a\text{,}\text{}n)=1\text{,}\text{}$ then

Proof. The proof of this theorem is almost the same as the one given for Fermat’s theorem. Let $S$ be the set of integers $1\le x\le n$ with $gcd(x\text{,}\text{}n)=1\text{.}$ Let $\psi :S\to S$ be defined by $\psi (x)\equiv ax\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}n)\text{.}$ As in the proof of Fermat’s theorem, the numbers $\psi (x)$ for $x\in S$ are the numbers in $S$ written in some order. Therefore,

Dividing out the factors $x\in S\text{,}\text{}$ we are left with $1\equiv {a}^{\varphi (n)}\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}n)\text{.}$

Note that when $n=p$ is prime, Euler’s theorem is the same as Fermat’s theorem.

# Example

What are the last three digits of ${7}^{803}$?

SOLUTION

Knowing the last three digits is the same as working mod 1000. Since $\varphi (1000)=1000(1-{\displaystyle \frac{1}{2}})(1-{\displaystyle \frac{1}{5}})=400\text{,}\text{}$ we have ${7}^{803}=({7}^{400}{)}^{2}{7}^{3}\equiv {7}^{3}\equiv 343\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}1000)\text{.}$ Therefore, the last three digits are 343.

In this example, we were able to change the exponent 803 to 3 because $803\equiv 3\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}\varphi (1000))\text{.}$

# Example

Compute ${2}^{43210}\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}101)\text{.}$

SOLUTION

Note that 101 is prime. From Fermat’s theorem, we know that ${2}^{100}\equiv 1\phantom{\rule{negativethinmathspace}{0ex}}\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}101)\text{.}$ Therefore,

In this case, we were able to change the exponent 43210 to 10 because $43210\equiv 10\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}100)\text{.}$

To summarize, we state the following, which is a generalization of what we know for primes:

# Basic Principle

Let $a\text{,}\text{}n\text{,}\text{}x\text{,}\text{}y$ be integers with $n\ge 1$ and $gcd(a\text{,}\text{}n)=1\text{.}$ If $x\equiv y\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}\varphi (n))\text{,}\text{}$ then ${a}^{x}\equiv {a}^{y}\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}n)\text{.}$ In other words, if you want to work mod $n\text{,}\text{}$ you should work mod $\varphi (n)$ in the exponent.

Proof. Write $x=y+\varphi (n)k\text{.}$ Then

This completes the proof.

This extremely important fact will be used repeatedly in the remainder of the book. Review the preceding examples until you are convinced that the exponents mod $400=\varphi (1000)$ and mod $100$ are what count (i.e., don’t be one of the many people who mistakenly try to work with the exponents mod 1000 and mod 101 in these examples).

# 3.6.1 Three-Pass Protocol

Alice wishes to transfer a secret key $K$ (or any short message) to Bob via communication on a public channel. The Basic Principle can be used to solve this problem.

First, here is a nonmathematical way to do it. Alice puts $K$ into a box and puts her lock on the box. She sends the locked box to Bob, who puts his lock on the box and sends the box back to Alice. Alice then takes her lock off and sends the box to Bob. Bob takes his lock off, opens the box, and finds $K\text{.}$

Here is the mathematical realization of the method. First, Alice chooses a large prime number $p$ that is large enough to represent the key $K\text{.}$ For example, if Alice were trying to send a 56-bit key, she would need a prime number that is at least 56 bits long. However, for security purposes (to make what is known as the discrete log problem hard), she would want to choose a prime significantly longer than 56 bits. Alice publishes $p$ so that Bob (or anyone else) can download it. Bob downloads $p\text{.}$ Alice and Bob now do the following:

Alice selects a random number $a$ with $gcd(a\text{,}\text{}p-1)=1$ and Bob selects a random number $b$ with $gcd(b\text{,}\text{}p-1)=1\text{.}$ We will denote by ${a}^{-1}$ and ${b}^{-1}$ the inverses of $a$ and $b$ mod $p-1\text{.}$

Alice sends ${K}_{1}\equiv {K}^{a}\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}p)$ to Bob.

Bob sends ${K}_{2}\equiv {K}_{1}^{b}\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}p)$ to Alice.

Alice sends ${K}_{3}\equiv {K}_{2}^{{a}^{-1}}\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}p)$ to Bob.

Bob computes $K\equiv {K}_{3}^{{b}^{-1}}\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}p)\text{.}$

At the end of this protocol, both Alice and Bob have the key $K\text{.}$

The reason this works is that Bob has computed ${K}^{ab{a}^{-1}{b}^{-1}}\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}p)\text{.}$ Since $a{a}^{-1}\equiv b{b}^{-1}\equiv 1\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}p-1)\text{,}\text{}$ the Basic Principle implies that ${K}^{ab{a}^{-1}{b}^{-1}}\equiv {K}^{1}\equiv K\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}p)\text{.}$

The procedure is usually attributed to Shamir and to Massey and Omura. One drawback is that it requires multiple communications between Alice and Bob. Also, it is vulnerable to the intruder-in-the-middle attack (see Chapter 15).