1.25: Primality Tests

Two theorems from the previous chapter, Wilson’s Theorem and Fermat’s Little Theorem, connect prime numbers and congruences in perhaps surprising ways. In this chapter we look at how these theorems can be turned into techniques for testing whether a number \(n\) is prime. Those tests will differ quite a bit from the first, simplest means of testing primes we describe below, which is based on Section 1.11 and specifically Theorem 1.11.2:

Primality Test #1

Given an integer \(n \geq 2\), determine whether \(n\) is divisible by any integer in \(2,\dots,\lfloor\sqrt{n}\rfloor\) (more specifically, by any prime number in this range). If so, then \(n\) is not prime; otherwise, \(n\) is prime.

Now we use the theorems from the last chapter.

A Primality Test Using Wilson’s Theorem

To introduce our next test, observe the following.

• If \(n\) is prime, then \((n-1)! \equiv -1 \pmod n\) (this is Wilson’s Theorem).
• If \(n=4\), then \((n-1)!\equiv 1 \pmod n\); if instead \(n \neq 4\) but \(n\) is not prime, then \((n-1)! \equiv 0 \pmod n\) (see Exercise 1.24.1).

Hence an integer \(n \geq 2\) is prime if and only if \((n-1)! \equiv -1 \pmod n\). This gives us a test.

Primality Test #2

Given an integer \(n \geq 2\), determine whether \((n-1)! \equiv -1 \pmod n\). If so, \(n\) is prime; if not, then \(n\) is composite.

For example, \(4! = 24\), which is congruent to \(-1\) modulo 5, so this test guarantees that \(5\) is prime; meanwhile, \(11! = 39916800 \equiv 0 \pmod {12}\), so the test shows that \(12\) is not a prime number.

One big drawback of Primality Test #2 is that there does not seem to be a generally applicable way to efficiently compute \((n-1)!\) modulo \(n\) for large \(n\). For instance \(15!\) rounds to \(1.3076744\times 10^{12}\), and \(20!\) rounds to \(2.432902 \times 10^{18}\); the factorial numbers \(n!\) are very large even for relatively small \(n\). We can compute \((n-1)! \bmod n\) by reducing modulo \(n\) after every multiplication; for instance, we compute \(8! \mod 9\) by \[\begin{aligned} 1 \bmod 9 &= 1;\\ (2\cdot 1) \bmod 9 &= 2;\\ (3\cdot 2\cdot 1) \bmod 9 &= (3 \cdot 2)\bmod 9 = 6;\\ (4 \cdot 3\cdot 2\cdot 1) \bmod 9 &= (4 \cdot 6)\bmod 9 = 6;\\ (5 \cdot 4 \cdot 3 \cdot 2 \cdot 1) \bmod 9 &= (5 \cdot 6)\bmod 9 = 3;\\ (6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1) \bmod 9 &= (6 \cdot 3)\bmod 9 = 0;\\ (7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1) \bmod 9 &= (7 \cdot 0)\bmod 9 = 0;\\ (8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1) \bmod 9 &= (8 \cdot 0)\bmod 9 = 0.\end{aligned}\] However, note that each line of such a calculation requires one more multiplication and one more application of “mod.” Hence testing whether \((n-1)! \equiv -1 \pmod n\) in this way takes a number of steps that is proportional to \(n\), so as \(n\) gets larger and larger, we would expect this primality test to take longer and longer to perform (whether it is carried out by a human or a computer).

In contrast, note that the number of steps necessary to carry out Primality Test #1 is proportional to \(\sqrt{n}\), so Primality Test #1 may take less time to apply than Primality Test #2, especially if \(n\) is large. Hence Wilson’s Theorem, while it does give us a new test for primality, hasn’t given us a great test for primality.

We wonder—can we find a still better test for primality?

A Primality Test Using Fermat’s Little Theorem

According to Fermat’s Little Theorem, if \(p\) is prime and \(1\le a\le p-1\), then \[a^{p-1}\equiv 1\pmod p.\nonumber \] The converse is also true in the following sense:

Theorem \(\PageIndex{1}\): Fermat's Little Theorem Converse

If \(m\ge 2\) and for all \(a\) such that \(1\le a\le m-1\) we have \[a^{m-1}\equiv 1\pmod m\nonumber \] then \(m\) must be prime.

Proof

If the hypothesis holds, then for all \(a\) with \(1\le a\le m-1\), we know that \(a\) has an inverse modulo \(m\), namely, \(a^{m-2}\) is an inverse for \(a\) modulo \(m\). By Theorem 1.20.2, this says that for \(1\le a\le m-1\), \(\gcd(a,m)=1\). But if \(m\) were not prime, then we would have \(m=ab\) with \(1<a<m\), \(1<b<m\). Then \(\gcd(a,m)=a>1\), a contradiction. So \(m\) must be prime.

We can turn this into a test for primality.

Primality Test #3

Given an integer \(n \geq 2\), for each \(a\) between \(1\) and \(n-1\), test whether \(a^{n-1}\equiv 1 \pmod n\). If the congruence is true for every value of \(a\), then \(n\) is prime. If the congruence fails for any value of \(a\) between \(1\) and \(n-1\), then \(n\) is not prime.

As an example, using Primality Test #3 to decide whether 13 is prime, we would verify the following:

\(1^{12} = 1 \equiv 1 \pmod {13}\);		\(7^{12} = 13841287201 \equiv 1 \pmod {13}\);
\(2^{12} = 4096 \equiv 1 \pmod {13}\);		\(8^{12} = 68719476736 \equiv 1 \pmod {13}\);
\(3^{12} = 531441 \equiv 1 \pmod {13}\);		\(9^{12} = 282429536481 \equiv 1 \pmod {13}\);
\(4^{12} = 16777216 \equiv 1 \pmod {13}\);		\(10^{12} = 1000000000000 \equiv 1 \pmod {13}\);
\(5^{12} = 244140625 \equiv 1 \pmod {13}\);		\(11^{12} = 3.1384284... \times 10^{12} \equiv 1 \pmod {13}\);
\(6^{12} = 2176782336 \equiv 1 \pmod {13}\);		\(12^{12} = 8.9161004... \times 10^{12} \equiv 1 \pmod {13}\).

Primality Tests Using Fermat’s Little Theorem, Continued

Using Primality Test #3 to check that \(p\) is prime, we would have to check that \(a^{p-1}\equiv 1\pmod{p}\) for \(a=1,2,3,\dotsc,p-1\). As the last example showed, this is a lot of work.

What if \(n>2\) and we knew that \(2^{n-1}\equiv 1\pmod n\), though we didn’t know what \(a^{n-1}\) was congruent to modulo \(n\) for other values of \(a\)? Could we conclude that \(n\) was prime?

Unfortunately, the answer is no. For example, look at \(n=341\). This number is not prime (why not?). Still, it is true that \(2^{341-1}\equiv 1\pmod {341}\) (see Exercise \(\PageIndex{1}\)).

The moral is that even if \(2^{n-1}\equiv 1\pmod n\), the number \(n\) need not be prime.\(^{1}\) To be absolutely certain that \(n\) was prime using Fermat’s Little Theorem and Theorem \(\PageIndex{1}\), we would need to check whether \(a^{n-1}\equiv 1\pmod n\) for all integers \(a\) in \(2,3,\dots,n-1\).

On the other hand, consider the case of \(m=63\). Note that \[2^6=64\equiv 1\pmod{63}.\nonumber \]

Hence, \(2^6\equiv 1\pmod{63}\). Raising both sides to the \(10\)th power we have \[2^{60}\equiv 1\pmod{63}.\nonumber \] Then multiplying both sides by \(2^2\) we get \[2^{62}\equiv 4\pmod{63}.\nonumber \] Since \[4\not\equiv 1\pmod{63},\nonumber \] we have \[2^{62}\not\equiv 1\pmod{63}.\nonumber \] This tells us that \(63\) is not prime, without factoring \(63\). We emphasize that in general if \(2^{m-1} \not\equiv 1 \pmod m\) then we can be sure that \(m\) is not prime.

Can we turn this into a test (or partial test) for primality? Let’s look at some experimental data.

FACT.

There are \(455\),\(052\),\(511\) odd primes \(p\le 10^{10}\), all of which satisfy \(2^{p-1}\equiv 1\pmod p\). There are only \(14\),\(884\) composite numbers \(2<n\le 10^{10}\) that satisfy \(2^{n-1}\equiv 1\pmod n\). Thus, if \(2<n\le 10^{10}\) and \(n\) satisfies \(2^{n-1}\equiv 1\pmod n\), the probability that \(n\) is prime is \[\frac{455,052,511}{455,052,511+14,884}\approx .999967292.\nonumber \] In other words, if you find that \(2^{n-1}\equiv 1\pmod n\), then it is highly likely (but not a certainty) that \(n\) is prime, at least when \(n\le 10^{10}\).

Thus, unlike the previous three primality tests in this chapter, our next primality test is a probabilistic primality test.

Primality Test #4

Given an integer \(n > 2\), test whether \(2^{n-1}\equiv 1 \pmod n\). If not, then \(n\) is \(\underline{\text{definitely}}\) not prime. If \(2^{n-1}\equiv 1 \pmod n\), then \(n\) is \(\underline{\text{probably}}\) prime.

One might ask what happens if we use 3 instead of 2 in the above probabilistic primality test. Or, better yet, what if we evaluate \(a^{m-1} \bmod m\) for several different values of \(a\). Consider the following data:

• The number of primes \(p\le 10^6\) is 78,498.
• The number of composite numbers \(n\le 10^6\) such that \(2^{n-1}\equiv 1\pmod n\) is \(245\).
• The number of composite numbers \(n\le 10^6\) such that \(2^{n-1}\equiv 1\pmod n\) \(\underline{\text{and}}\) \(3^{n-1}\equiv 1\pmod n\) is 66.
• The number of composite numbers \(n\le 10^6\) such that \(a^{n-1}\equiv 1\pmod n\) for \(\underline{\text{all}}\) \(a \in \{2,3,5,7,11,13,17,19,31,37,41\}\) is 0.

Pausing here, we have the another probabilistic primality test, more elaborate than the last:

Primality Test #5

Given an integer \(n > 2\), test whether \(a^{n-1}\equiv 1\pmod n\) for \(a\in\{2,3,5,7,11,13,17,19,31,37,41\}\) such that \(n \nmid a\). If the congruences are not true for all these \(a\), then \(n\) is \(\underline{\text{definitely}}\) not prime. If the congruences are all true, then \(n\) is \(\underline{\text{definitely}}\) prime if \(n\le 10^6\) and \(\underline{\text{probably}}\) prime (highly likely) if \(n >10^6\).

Conclusion

In practice, there are better probabilistic primality tests than the ones mentioned in this chapter, using more efficient approaches than our applications of Wilson’s Theorem and Fermat’s Little Theorem. For more details see, for example, Elementary Number Theory, fourth edition, by Kenneth Rosen.

Computer algebra systems such as Maple run very sophisticated probabilistic primality tests (the computations for numbers \(n \leq 10^6\) above were computed using Maple). For example, Maple’s command isprime(n) returns false if \(n\) is not prime and returns true if \(n\) is probably prime. (The underlying primality test used by isprime uses a somewhat different idea than our probilistic tests above.) While ideally we would like to eliminate all uncertainty from the results of a test like isprime(n), so far no one has found an integer \(n\) for which isprime(n) gives the wrong answer.

In this chapter, our first three primality tests gave definite answers but took many steps to complete. The primality tests in the last section gave probable, but not always certain, answers using much less work.\(^{2}\) In theory it is possible remove all uncertainty from our primality testing using an algorithm requiring a number of steps proportional to the number of digits in \(n\) (recall from Exercise 1.6.11 that the number of digits in \(n\) is proportional to \(\log n\)). This is by using the Agrawal–Kayal–Saxena, or AKS, primality test, which was published in 2002 and won its authors multiple prestigious prizes, since it was the first primality test to accomplish all that it does. Note that the AKS test is of great theoretical importance, but in practice it is not used much at all—there are much more efficient ways of testing the primality of \(n\).

We end this chapter with an invitation: Do a little research of your own, online or otherwise...What can you find out about the current state of the art in primality testing?

Exercises

Exercise \(\PageIndex{1}\)

Use a computer (or do it via hand and/or calculator) to verify that \(2^{340} \equiv 1 \pmod {341}\) and that 341 is not prime. (Hint: for faster calculations, start by determining \(2^{10}\bmod 341\).)

Exercise \(\PageIndex{2}\)

Use a computer (or do it via hand and/or calculator) to show that

1. \(3^{90}\equiv 1\pmod{91}\), but \(91\) is not prime.
2. \(2^{n-1}\equiv 1\pmod n\) and \(3^{n-1}\equiv 1\pmod n\) for \(n=1105\), but \(1105\) is not prime.

(Hint: note that \(a^k\equiv 1\pmod n \ \ \Leftrightarrow \ \ a^k\bmod n=1\).)

Exercise \(\PageIndex{3}\)

Demonstrate the five primality tests from this chapter using the number \(n=11\), showing all computations and the determination of each test. Then repeat these same five tests for \(n=12\).

Footnotes

[1] If \(n\) is composite but \(a^{n-1}= 1\) \((\pmod n)\) for some \(a\) that is relatively prime to \(n\), we call \(n\) a Fermat pseudoprime.

[2] One thing we have not commented on is how much work is involved in raising an integer \(a\) to a high exponent like \(n-1\), when \(n\) is large. This turns out to need less work than you might think. Stay tuned for the next chapter!