A variant $n+1$ primality test

Last time I discussed the $n - 1$ and $n + 1$ primality tests. Recall that the $n - 1$ test says that $n$ is prime if there exists an $a \in Z_{n}^{*}$ such that

\begin{aligned} a^{n - 1} & \equiv 1 (\mod n) \\ a^{(n - 1) / p} & ≢ 1 (\mod n) \end{aligned}

for all primes $p$ which divide $n - 1$ .

The $n + 1$ can be stated in a similar form, and says that $n$ is prime if it is odd and there exists an $a \in (Z [\sqrt{d}])^{*}$ with $(\frac{d}{n}) = - 1$ such that

\begin{aligned} a^{n + 1} & \equiv 1 (\mod n) \\ a^{(n + 1) / p} & ≢ 1 (\mod n) \end{aligned}

for all primes $p$ which divide $n + 1$ .

I state it in this form to make the connection with the $n - 1$ test, but I’ve done a little sleight-of-hand in the presentation. In the first test $a$ is a unit of $Z_{n}$ , while in the second test $a$ is a unit of $Z [\sqrt{d}]$ (not $Z_{n} [\sqrt{d}]$ ). That is, the norm of $a$ in $Q (\sqrt{d})$ is $1$ ; this is a rather restrictive condition. In fact, when $d < - 3$ the only units of $Z [\sqrt{d}]$ are $\pm 1$ , and both of these will fail the second condition since $(n + 1) / p$ will be even for some $p$ .

When $d$ is positive and squarefree the situation is a little better in that there are an infinite number of units in $Z [\sqrt{d}]$ . However, these units are all of the form $\pm ϵ^{k}$ for some fundamental unit $ϵ := x + y \sqrt{d}$ (this may be found by solving Pell’s equation $x^{2} - d y^{2} = 1$ ). If the fundamental unit doesn’t satisfy the conditions then any power of it will also necessarily fail, so for any given value of $d$ there is essentially only one possible choice of $a$ which could work. On the upside, one could simply look up this choice in a table when $d$ is small; e.g., for $d := 3$ one should use $a := 2 + \sqrt{3}$ .

So that’s an unfortunate condition which isn’t present in the $n - 1$ test, but it’s necessary to be able to use Fermat’s theorem in $Z [\sqrt{d}]$ , which implies that if $p$ is prime and $a$ has norm $1$ then

a^{p - (d / p)} \equiv 1 (\mod p),

and more generally

a^{p^{e - 1} (p - (d / p))} \equiv 1 (\mod p^{e}) .

Now we’re ready to prove that the primality test works as stated. Let ${o r d}_{n, d} (a)$ denote the order of $a$ in $(Z_{n} [\sqrt{d}])^{*}$ , so the two conditions of the primality test tell us that ${o r d}_{n, d} (a) = n + 1$ .

Say $n$ has prime factorization $\prod_{i = 1}^{k} p_{i}^{e_{i}}$ . By the Chinese remainder theorem, we have

Z_{n} [\sqrt{d}] ≅ \prod_{i = 1}^{k} Z_{p_{i}^{e_{i}}} [\sqrt{d}],

n + 1 = {o r d}_{n, d} (a) = lcm ({o r d}_{p_{1}^{e_{1}}, d} (a), \dots, {o r d}_{p_{k}^{e_{k}}, d} (a))

and by Fermat’s theorem this divides

lcm (p_{1}^{e_{1} - 1} (p_{1} - (d / p_{1})), \dots, p_{k}^{e_{k} - 1} (p_{k} - (d / p_{k}))) .

Since each $p_{i}$ is odd, this equals

\begin{aligned} 2 lcm (p_{1}^{e_{1} - 1} \frac{p_{1} - (d / p_{1})}{2}, \dots, p_{k}^{e_{k} - 1} \frac{p_{k} - (d / p_{k})}{2}) \\ \leq 2 \prod_{i = 1}^{k} p_{i}^{e_{i} - 1} \frac{p_{i} - (d / p_{i})}{2} \\ \leq 2 n \prod_{i = 1}^{k} \frac{p_{i} + 1}{2 p_{i}} . \end{aligned}

Now, if $n$ has at least two distinct prime factors then this is at most

2 n \cdot \frac{3 + 1}{2 \cdot 3} \cdot \frac{5 + 1}{2 \cdot 5} = \frac{4}{5} n .

Thus we conclude that $n + 1 \leq 4 n / 5$ , a contradiction since $n$ is positive. Thus $n$ must have just one prime factor; say $n := p^{e}$ . Using Fermat’s theorem and the fact that $(\frac{d}{p}) = - 1$ (otherwise $(\frac{d}{n}) \neq - 1$ ), we have

n + 1 = {o r d}_{n, d} (a) ∣ p^{e - 1} (p + 1) = n + p^{e - 1} .

It follows that $n + 1 ∣ p^{e - 1} - 1 \leq n / 3$ , again a contradiction, unless $p^{e - 1} = 1$ , i.e., $e = 1$ and $n = p$ is prime.

I found this kind of argument in Prime Numbers and Computer Methods for Factorization (page 116). In that book it is applied to Lucas sequences, which simplifies some things, although can also obscure the group $F_{n^{2}}^{*}$ working in the background.

Blogarithm

Curtis' self-improvement blog

A variant $n + 1$ primality test