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