Determining if a number n$n$ is a prime number or not is an important problem in computational number theory. Two simple ways of proving primality rely on the prime factorizations of n−1$n-1$ and n+1$n+1$. In general finding these factorizations is probably a harder problem than testing the primality of n$n$, so the methods are only applicable in special cases, but are they are interesting nonetheless.

At a high level, the n−1$n-1$ method works by showing that a subgroup of Z∗n${\mathbb{Z}}_n^{\ast }$ is so large that n$n$ must be prime. Specifically, a subgroup of order n−1$n-1$ is demonstrated, which implies that Z∗n${\mathbb{Z}}_n^{\ast }$ is as large as possible, namely the full set of nonzero residues {1,2,…,n−1}$\{1,2,\dots ,n-1\}$; if even one element was missing then there would be less than n−1$n-1$ elements in Z∗n${\mathbb{Z}}_n^{\ast }$. But Z∗n={1,2,…,n−1}${\mathbb{Z}}_n^{\ast }=\{1,2,\dots ,n-1\}$ means that every positive integer strictly less than n$n$ is coprime to n$n$, and so n$n$ is prime.

To show that Z∗n${\mathbb{Z}}_n^{\ast }$ contains a subgroup of size n−1$n-1$, we find an element a∈Z∗n$a\in {\mathbb{Z}}_n^{\ast }$ whose order is n−1$n-1$ (such an element is called a primitive root). To do this, we show that

and

for all primes p$p$ which divide n−1$n-1$. This is enough to show that the order of a$a$ is n−1$n-1$; if the true order was r<n−1$r<n-1$ then using Bézout’s identity one would be able to derive agcd(r,n−1)≡1(modn)$a^{gcd(r,n-1)}\equiv 1(\mathrm{mod}n)$ and this would contradict (2) for some p$p$.

When n$n$ is prime, there isn’t any known efficient algorithm which is guaranteed to find a primitive root a$a$ satisfying (1) and (2), but in practice this isn’t a concern. In fact, there are φ(n−1)=Θ(n/lnlnn)$\phi (n-1)=\mathrm{\Theta }(n/\ln \ln n)$ primitive roots (where φ$\phi$ denotes Euler’s totient function), so if one simply tests if random a$a$ satisfies (1) and (2) then one should quickly find one which works, and thereby prove that n$n$ is prime. As mentioned, the real problem with applying this method in practice is finding the primes p$p$ which divide n−1$n-1$.

Incidentally, when n$n$ isn’t prime, this is usually easy to show since condition (1) will often fail to hold, and all primes satisfy (1) for all a∈Z∗n$a\in {\mathbb{Z}}_n^{\ast }$. However, some composite numbers still satisfy (1) for all a∈Z∗n$a\in {\mathbb{Z}}_n^{\ast }$. In such a case a more stringent form of (1) can be used to prove compositeness, and this method can be employed in practice since it only requires the “evenness factorization” n−1=2r⋅m$n-1=2^r\cdot m$ with m$m$ odd, which is simple to compute.

The n+1$n+1$ method is similar to the n−1$n-1$ method, except it works in the group (Zn[d−−√])∗$({\mathbb{Z}}_n[\sqrt{d}]{)}^{\ast }$, where d$d$ satisfies (dn)=−1$(\frac{d}{n})=-1$, i.e., d$d$ is not a quadratic residue mod n$n$. We assume that n$n$ is odd (otherwise the problem is trivial), so that in practice d$d$ can be found by computing the Jacobi symbol (dn)$(\frac{d}{n})$ for multiple values of d$d$ until one works. Note that when n$n$ is prime we have Zn[d−−√]≅Fn2${\mathbb{Z}}_n[\sqrt{d}]\cong {\mathbb{F}}_{n^2}$, the finite field of size n2$n^2$, so there still exist primitive roots a$a$ which generate (Zn[d−−√])∗$({\mathbb{Z}}_n[\sqrt{d}]{)}^{\ast }$. We’ll denote the conjugate of a$a$ by a¯$\overline{a}$, so if a:=b+cd−−√$a:=b+c\sqrt{d}$ with b$b$, c∈Zn$c\in {\mathbb{Z}}_n$ then a¯=b−cd−−√$\overline{a}=b-c\sqrt{d}$.

As you might expect in relation to the above, the n+1$n+1$ method finds a subgroup of (Zn[d−−√])∗$({\mathbb{Z}}_n[\sqrt{d}]{)}^{\ast }$ of size n+1$n+1$ by finding an a∈(Zn[d−−√])∗$a\in ({\mathbb{Z}}_n[\sqrt{d}]{)}^{\ast }$ which has order n+1$n+1$. Actually, we need something a bit stronger than this; we need to show

and

for all primes p$p$ which divide n+1$n+1$. Condition (4) not only implies that a(n+1)/p≢1(modn)$a^{(n+1)/p}\not\equiv 1(\mathrm{mod}n)$, but also that a(n+1)/p≢1(modq)$a^{(n+1)/p}\not\equiv 1(\mathrm{mod}q)$ where q$q$ is any prime divisor of n$n$. To see that this, we show the contrapositive. Suppose that q$q$ is a prime divisor of n$n$ and that q∣a(n+1)/p−1$q\mid a^{(n+1)/p}-1$.¹ It follows that q$q$ also divides (a(n+1)/p−1)(a¯(n+1)/p−1)∈Z$(a^{(n+1)/p}-1)({\overline{a}}^{(n+1)/p}-1)\in \mathbb{Z}$, and thus divides the gcd in (4), so (4) fails to hold.

Since condition (3) implies that an+1≡1(modq)$a^{n+1}\equiv 1(\mathrm{mod}q)$ and condition (4) implies that a(n+1)/p≢1(modq)$a^{(n+1)/p}\not\equiv 1(\mathrm{mod}q)$, just like before one knows that a(modq)$a(\mathrm{mod}q)$ has order n+1$n+1$. In particular, there must be at least n+1$n+1$ elements in (Zq[d−−√])∗$({\mathbb{Z}}_q[\sqrt{d}]{)}^{\ast }$.

Toward a contradiction, suppose that (3) and (4) hold and that n$n$ is not prime. Let q$q$ be the smallest prime divisor of n$n$, so that q2≤n$q^2\le n$. As we just saw, a(modq)$a(\mathrm{mod}q)$ has order n+1$n+1$, so we get the lower bound

However, Zq[d−−√]${\mathbb{Z}}_q[\sqrt{d}]$ has q2$q^2$ elements, and so

which contradicts the lower bound. Thus n$n$ must in fact be prime.

When n$n$ is prime, an a$a$ which satisfies (3) and (4) can be found by taking a primitive root of Fn2${\mathbb{F}}_{n^2}$ and raising it to the power n−1$n-1$, since in this case (an−1)n+1≡1(modn)$(a^{n-1}{)}^{n+1}\equiv 1(\mathrm{mod}n)$ and n$n$ will not divide (an−1)(n+1)/p−1$(a^{n-1}{)}^{(n+1)/p}-1$ or its conjugate. As mentioned, there isn’t a guaranteed procedure to find a primitive root, but since there are φ(n2−1)=Θ(n2/lnlnn)$\phi (n^2-1)=\mathrm{\Theta }(n^2/\ln \ln n)$ of them, in practice it shouldn’t be too hard to find one; the sticking point is finding the factorization of n+1$n+1$.

Incidentally, the n+1$n+1$ test is often presented using Lucas sequences rather than Fn2${\mathbb{F}}_{n^2}$. But that’s a topic for another post.