# 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  is a prime and  does not divide  then



Proof. Let



Consider the map  defined by  For example, when  and  the map  takes a number  multiplies it by 2, then reduces the result mod 7.

We need to check that if  then  is actually in  that is,  Suppose  Then  Since  we can divide this congruence by  to obtain  so  This contradiction means that  cannot be 0, hence  Now suppose there are  with  This means  Since  we can divide this congruence by  to obtain  We conclude that if  are distinct elements of  then  and  are distinct. Therefore,



are distinct elements of  Since  has only  elements, these must be the elements of  written in a some order. It follows that



Since  for  we can divide this congruence by  What remains is 

# Example

 From this we can evaluate  Write  Note that when working mod 11, we are essentially working with the exponents mod 10, not mod 11. In other words, from  we deduce 

The example leads us to a very important fact:

# Basic Principle

Let  be prime and let  be integers with  If  then  In other words, if you want to work mod  you should work mod  in the exponent.

Proof. Write  Then



This completes the proof.

In the rest of this book, almost every time you see a congruence mod  it will involve numbers that appear in exponents. The Basic Principle that was just stated shows that this translates into an overall congruence mod  Do not make the (unfortunately, very common) mistake of working mod  in the exponent with the hope that it will yield an overall congruence mod  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 ). Note that we showed that a factorization must exist, even though we didn’t find the factors.

Usually, if  the number  is prime. However, there are exceptions:  is composite but  We can see this as follows: Since  we have  Similarly, since  and  we can conclude that  and  Putting things together via the Chinese remainder theorem, we find that 

Another such exception is  However, these exceptions are fairly rare in practice. Therefore, if  it is quite likely that  is prime. Of course, if  then  cannot be prime.

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

For example, suppose we want to find a random 300-digit prime. Choose a random 300-digit odd integer  as a starting point. Successively, for each odd integer  compute  by the modular exponentiation technique of Section 3.5. If  Fermat’s theorem guarantees that  is not prime. This will probably throw out all the composites encountered. When you find an  with  you probably have a prime number. But how many  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  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  Let  be the number of integers  such that  For example, if  then there are four such integers, namely 1,3,7,9. Therefore,  Often  is called Euler’s -function.

If  is a prime and  then we must remove every th number in order to get the list of ’s with  which yields



In particular,



More generally, it can be deduced from the Chinese remainder theorem that for any integer 



where the product is over the distinct primes  dividing  When  is the product of two distinct primes, this yields






# Euler’s Theorem

If  then



Proof. The proof of this theorem is almost the same as the one given for Fermat’s theorem. Let  be the set of integers  with  Let  be defined by  As in the proof of Fermat’s theorem, the numbers  for  are the numbers in  written in some order. Therefore,



Dividing out the factors  we are left with 

Note that when  is prime, Euler’s theorem is the same as Fermat’s theorem.

# Example

What are the last three digits of ?

SOLUTION

Knowing the last three digits is the same as working mod 1000. Since  we have  Therefore, the last three digits are 343.

In this example, we were able to change the exponent 803 to 3 because 

# Example

Compute 

SOLUTION

Note that 101 is prime. From Fermat’s theorem, we know that  Therefore,



In this case, we were able to change the exponent 43210 to 10 because 

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

# Basic Principle

Let  be integers with  and  If  then  In other words, if you want to work mod  you should work mod  in the exponent.

Proof. Write  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  and mod  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  (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  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 

Here is the mathematical realization of the method. First, Alice chooses a large prime number  that is large enough to represent the key  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  so that Bob (or anyone else) can download it. Bob downloads  Alice and Bob now do the following:

1. Alice selects a random number  with  and Bob selects a random number  with  We will denote by  and  the inverses of  and  mod 

2. Alice sends  to Bob.

3. Bob sends  to Alice.

4. Alice sends  to Bob.

5. Bob computes 

At the end of this protocol, both Alice and Bob have the key 

The reason this works is that Bob has computed  Since  the Basic Principle implies that 

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).