Determining if a number $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$ and $n+1$. In general finding these factorizations is probably a harder problem than testing the primality of $n$, so the methods are only applicable in special cases, but are they are interesting nonetheless.

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

To show that $\Z_n^*$ contains a subgroup of size $n-1$, we find an element $a\in\Z_n^*$ whose order is $n-1$ (such an element is called a primitive root). To do this, we show that

\[ a^{n-1} \equiv 1 \pmod{n} \tag{1} \]

and

\[ a^{(n-1)/p} \not\equiv 1 \pmod{n} \tag{2} \]

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

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

Incidentally, when $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\in\Z_n^*$. However, some composite numbers still satisfy (1) for all $a\in\Z_n^*$. 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=2^r\cdot m$ with $m$ odd, which is simple to compute.

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

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

\[ a^{n+1} \equiv 1 \pmod{n} \tag{3} \]

and

\[ \gcd((a^{(n+1)/p}-1)(\bar{a}^{(n+1)/p}-1),n)=1 \tag{4} \]

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

Since condition (3) implies that $a^{n+1}\equiv1\pmod{q}$ and condition (4) implies that $a^{(n+1)/p}\not\equiv1\pmod{q}$, just like before one knows that $a\pmod{q}$ has order $n+1$. In particular, there must be at least $n+1$ elements in $(\Z_q[\sqrt{d}])^*$.

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

\[ n+1 \leq \lvert(\Z_q[\sqrt{d}])^*\rvert . \]

However, $\Z_q[\sqrt{d}]$ has $q^2$ elements, and so

\[ \lvert(\Z_q[\sqrt{d}])^*\rvert \leq q^2-1 \leq n-1 , \]

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

When $n$ is prime, an $a$ which satisfies (3) and (4) can be found by taking a primitive root of $\F_{n^2}$ and raising it to the power $n-1$, since in this case $(a^{n-1})^{n+1}\equiv1\pmod{n}$ and $n$ will not divide $(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 $\varphi(n^2-1)=\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$.

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