5.3: Fermat’s Little Theorem and Primality Testing

Euler’s theorem has many other important consequences. It implies what is known as Fermat’s little theorem, although it was not proved by Fermat himself, since, as he writes in the letter in which he stated the result, he feared “going on too long”. Not an isolated case, it would appear!

Corollary 5.8 (Fermat's Little Theorem)

If \(p\) is prime and \(\gcd(a, p) = 1\), then \(a^{p-1} = _{p} 1\).

This follows from Euler’s Theorem by noticing that for a prime \(p\), \(\varphi (p) = p-1\). There is an equivalent formulation which allows \(p\) to be a divisor of \(a\). Namely, if \(p\) is prime, then \(a^{p} = _{p} a\). Notice that if \(p | a\), then both sides are congruent to \(0\).

Primes are of great theoretical and practical value (think of encryption, for example). Algorithms for primality testing are therefore very useful. The simplest test to find out if some large number \(\sqrt{n}\) is prime, consists of course of applying some version of Eratosthenes’ sieve to the positive integers less than or equal to \(n\). By the prime number theorem (Theorem 2.21), this will give on the order of \(\frac{2\sqrt{n}}{ln n}\) primes. Then divide \(n\) by all these numbers. This will take on the order of \(\frac{2\sqrt{n}}{ln n}\) divisions.

Another possibility is to use the converse of Fermat’s little theorem (Corollary 5.8). If \(n\) and \(p\) are distinct primes, we know that \(p^{n-1} = _{n} 1\). The Fermat primality test for \(n\) consists of testing for example whether \(2^{n-1} = _{n} 1\). However, the converse of Fermat’s little theorem is not true! So even if \(2^{n-1} = _{n} 1\), it could be that \(n\) is not prime; we will discuss this possibility at the end of this section. As it turns out, primality testing via Fermat’s little theorem can be done much faster than the naive method, provided one uses fast modular exponentiation algorithms. We briefly illustrate this technique by computing \(11^{340}\) modulo \(341\).

Start by expanding \(340\) in base \(2\) as done in exercise 3.18, where it was shown that this takes on the order of \(\mbox{log}_{2} 340\) (long) divisions.

\[340 = 170 \cdot 2+\textbf{0} \nonumber\]

\[170 = 85 \cdot 2+\textbf{0} \nonumber\]

\[85 = 42 \cdot 2+\textbf{1} \nonumber\]

\[42 = 21 \cdot 2+\textbf{0} \nonumber\]

\[21 = 10 \cdot 2+\textbf{1} \nonumber\]

\[10 = 5 \cdot 2+\textbf{0} \nonumber\]

\[5 = 2 \cdot 2+\textbf{1} \nonumber\]

\[2 = 1 \cdot 2+\textbf{0} \nonumber\]

\[1 = 0 \cdot 2+\textbf{1} \nonumber\]

And so

\[\begin{array} {cc} {340 = 101010100}&{\mbox{in base } 2} \nonumber \end{array}\]

Next, compute a table of powers \(11^{2^{i}}\) modulo \(341\), as done below. By doing this from the bottom up, this can be done using very few computations. For instance, once \(11^{8} = _{341} 143\) has been established, the next up is found by computing \(143^2\) modulo \(341\), which gives \(330\), and so on. So this takes about \(\mbox{log}_{2} 340\) multiplications.

\[\begin{array}{ll} {1}&{11^256 = _{341} 330}\\ {0}&{11^128 = _{341} 143}\\ {1}&{11^{64} =_{341} 319}\\ {0}&{11^{32} = _{341} 121}\\ {1}&{11^{16} = _{341} 330}\\ {0}&{11^8 = _{341} 143}\\ {1}&{11^4 = _{341} 319}\\ {0}&{11^2 = _{341} 121}\\ {0}&{11^1 = _{341} 11} \end{array}\]

The first column in the table thus obtained now tells us which coefficients in the second we need to compute the result.

\[11^{340} = _{341} 330 \cdot 319 \cdot 330 \cdot 319 = _{341} 132 \nonumber\]

Again, this takes no more than \(\mbox{log}_{2} 340\) multiplications. Thus altogether, for a number \(x\) and a computation in base \(b\), this takes on the order of \(2 \mbox{log}_{b} x\) multiplications plus \(\mbox{log}_{b} x\) divisions. For large numbers, this is much more efficient than the \(\sqrt{x}\) of the naive method.

The drawback is that we can get false positives.

Definition 5.9

The number \(n \in \mathbb{N}\) is called a pseudoprime to the base a if \(\gcd (a, n) = 1\) and \(a^{n-1} = _{n} 1\) but nonetheless \(n\) is composite. (When the base is \(2\), the clause to the base \(2\) is often dropped.)

Some numbers pass all tests to every base and are still composite. These are called Carmichael numbers. The smallest Carmichael number is 561. It has been proved [7] that there are infinitely many of them.

Definition 5.10

The number \(n \in \mathbb{N}\) is called a Carmichael number if it is composite and it is a pseudoprime to every base.

The smallest pseudoprime is \(341\), because \(2^{340} = _{341} 1\) while \(341 = 11 \cdot 31\). In this case, one can still show that \(341\) is not a prime by using a different base \(3^{340} = _{341} 56\). By Fermat's little theorem, \(341\) cannot be prime.

The reason that the method sketched here is still useful is that pseudoprime are very much rarer than primes. The number below \(2.5 \cdot 10^{10}\) contain on the order of \(10^{9}\) primes. At the same time, this set contains only \(21853\) pseudoprimes to the prime \(2\). There are only \(1770\) integers below \(2.5 \cdot 10^{10}\) that are pseudoprime to the base \(2, 3, 5\), and \(7\). Thus if a number passes these four tests, it is overwhelmingly likely that it is a prime.