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 $\newcommand{\Z}{\mathbb{Z}}a\in\Z^*_n$ such that

\begin{align}

a^{n-1} &\equiv 1 \pmod{n} \\

a^{(n-1)/p} &\not\equiv 1 \pmod{n}

\end{align}

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{align}

a^{n+1} &\equiv 1 \pmod{n} \\

a^{(n+1)/p} &\not\equiv 1 \pmod{n}

\end{align}

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 $\mathbb{Q}(\sqrt{d})$ is $1$; this is a rather restrictive condition. In fact, when $d<-3$ the only units of $\Z[\sqrt{d}]$ are $\pm1$, 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\epsilon^k$ for some *fundamental unit* $\epsilon:=x+y\sqrt{d}$ (this may be found by solving Pell’s equation $x^2-dy^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 \pmod{p} , \]

and more generally

\[ a^{p^{e-1}(p-(d/p))} \equiv 1 \pmod{p^e} . \]

Now we’re ready to prove that the primality test works as stated. Let $\newcommand{\ord}{\mathop{\mathrm{ord}}\nolimits}\ord_{n,d}(a)$ denote the order of $a$ in $(\Z_n[\sqrt{d}])^*$, so the two conditions of the primality test tell us that $\ord_{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}] \cong \prod_{i=1}^k \Z_{p_i^{e_i}}[\sqrt{d}] , \]

so

\[ n+1 = \ord_{n,d}(a) = \DeclareMathOperator{\lcm}{lcm}\lcm(\ord_{p_1^{e_1},d}(a),\dotsc,\ord_{p_k^{e_k},d}(a)) \]

and by Fermat’s theorem this divides

\[ \lcm(p_1^{e_1-1}(p_1-(d/p_1)),\dotsc,p_k^{e_k-1}(p_k-(d/p_k))) . \]

Since each $p_i$ is odd, this equals

\begin{align}

&\mathrel{\phantom{=}}2\lcm\Bigl(p_1^{e_1-1}\frac{p_1-(d/p_1)}{2},\dotsc,p_k^{e_k-1}\frac{p_k-(d/p_k)}{2}\Bigr) \\

&\leq 2\prod_{i=1}^k p_i^{e_i-1}\frac{p_i-(d/p_i)}{2} \\

&\leq 2n\prod_{i=1}^k\frac{p_i+1}{2p_i} .

\end{align}

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

\[ 2n\cdot\frac{3+1}{2\cdot3}\cdot\frac{5+1}{2\cdot5} = \frac{4}{5}n . \]

Thus we conclude that $n+1\leq4n/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 = \ord_{n,d}(a) \mid p^{e-1}(p+1) = n+p^{e-1} . \]

It follows that $n+1\mid 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 $\mathbb{F}_{n^2}^*$ working in the background.