1.24: Probabilistic Primality Tests

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}\)

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

Using the above theorem 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\). This is a lot of work. Suppose we just know that \(2^{m-1}\equiv 1\pmod m\) for some \(m>2\). Must \(m\) be prime? Unfortunately, the answer is no. The smallest composite \(m\) satisfying \(2^{m-1}\equiv 1\pmod m\) is \(m=341\).

Exercise \(\PageIndex{1}\)

Use Maple (or do it via hand and or calculator) to verify that \(2^{340} \equiv 1 \pmod {341}\) and that 341 is not prime.

The moral is that even if \(2^{m-1}\equiv 1\pmod m\), the number \(m\) need not be prime.

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 \[\boxed{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.

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<m\le 10^{10}\) that satisfy \(2^{m-1}\equiv 1\pmod m\). Thus, if \(2<m\le 10^{10}\) and \(m\) satisfies \(2^{m-1}\equiv 1\pmod m\), the probability \(m\) is prime is \[\frac{455,052,511}{455,052,511+14,884}\approx .999967292.\nonumber \] In other words, if you find that \(2^{m-1}\equiv 1\pmod m\), then it is highly likely (but not a certainty) that \(m\) is prime, at least when \(m\le 10^{10}\). Thus the following Maple procedure will almost always give the correct answer:

 > is_prob_prime:=proc(n)
     if n <=1  or Power(2,n-1) mod n <> 1 then 
        return "not prime"; 
     else
        return "probably prime";
     end if;
  end proc:

Note that the Maple command Power(a,n-1) mod n is an efficient way to compute \(a^{n-1} \bmod n\). We discuss this in more detail later. The procedure is_prob_prime(n) just defined returns “probably prime” if \(2^{n-1} \bmod n = 1\) and “not prime” if \(n \le 1\) or if \(2^{n-1} \bmod n \neq 1\). If the answer is “not prime”, then we know definitely that \(n\) is not prime. If the answer is “probably prime”, we know that there is a very small probability that \(n\) is not prime.

In practice, there are better probabilistic primality tests than that mentioned above. For more details see, for example, “Elementary Number Theory,” Fourth Edition, by Kenneth Rosen.

The built-in Maple procedure isprime is a very sophisticated probabilistic primality test. The command isprime(n) returns false if \(n\) is not prime and returns true if \(n\) is probably prime. So far no one has found an integer \(n\) for which isprime(n) gives the wrong answer.

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 \(\le 10^6\) is 78,498.

The number of composite numbers \(m\le 10^6\) such that \(2^{m-1}\equiv 1\pmod m\) is \(245\).

The number of composite numbers \(m\le 10^6\) such that \(2^{m-1}\equiv 1\pmod m\) and \(3^{m-1}\equiv 1\pmod m\) is 66.

The number of composite numbers \(m\le 10^6\) such that \(a^{m-1}\equiv 1\pmod m\) for \(a \in \{2,3,5,7,11,13,17,19,31,37,41\}\) is 0.

Thus, we have the following result:

If \(m\le 10^6\) and \(a^{m-1}\equiv 1\pmod m\) for \(a\in\{2,3,5,7,11,17,19,31,37,41\}\), then \(m\) is prime.

The above results for \(m\le 10^6\) were found using Maple.

If \(m>10^6\) and \(a^{m-1}\equiv 1\pmod m\) for \(a \in \{2,3,5,7,11,17,19,31,37,41\}\), it is highly likely, but not certain, that \(m\) is prime. Actually the primality test isprime that is built into Maple uses a somewhat different idea.

Exercise \(\PageIndex{2}\)

Use Maple to show that

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

Hint

Note that \(a^n\equiv 1\pmod m\Leftrightarrow a^n\bmod m=1\). In Maple, \(3^{90}\) is written 3^90 and \(3^{90}\bmod 91\) is written 3^90 mod 91. A faster way to compute \(a^n\bmod m\) in Maple is to use the command Power(a,n) mod m . Recall that ifactor(m) is the command to factor \(m\).