# Primality test for specific class of $N=k \cdot 2^n+1$

Can you prove or disprove the following claim:

Let $$N=k \cdot 2^n+1$$ be a natural number that is not a perfect square such that $$2 \nmid k$$ , $$n>2$$ . Let $$c$$ be the smallest odd prime number such that $$\left(\frac{c}{N}\right)=-1$$ , where $$\left(\frac{}{}\right)$$ denotes a Jacobi symbol . Let $$z$$ be a real number of the form $$a+b\sqrt{c}$$ equal to the modular $$(1-\sqrt{c})^{(N-1)/2} \operatorname{mod} N$$ , then $$N$$ is prime iff $$a=b$$ .

You can run this test here. I have verified this claim for all $$k \in [1,1000]$$ with $$n \in [3,1000]$$ .

• This looks rather similar to the Proth test for the same type of number. – Carl Schildkraut Sep 1 at 7:41
• @CarlSchildkraut Note that there is condition $k<2^n$ in Proth test. – Peđa Terzić Sep 1 at 7:45
• This should be equivalent to simply $(1-\sqrt{c})^{(N+1)/2}$ having a zero $\sqrt{c}$ coefficient. – Carl Schildkraut Sep 1 at 7:49
• Also, where are you using $k$ and $n$? If it just that $N$ must be $1\bmod 8$? – Carl Schildkraut Sep 1 at 7:57
• @CarlSchildkraut I wrote number $N$ in the given form because of condition $n>2$ . – Peđa Terzić Sep 1 at 8:01

This fails for $$N=22577=1411\cdot 2^4+1=107\cdot 211$$. The value of $$c$$ that is taken is $$3$$, but $$(1-\sqrt3)^{11288}\equiv 11502+11502\sqrt 3\bmod 22577.$$ It is true, however, if $$N$$ is prime. Setting $$x=\sqrt c$$, we have that $$x^N$$ is the Galois conjugate of $$x$$, so $$x^N=-x$$, whence $$(1+x)^{N+1}+(1+x)^N(1+x)=(1+x)(1+x^N)=(1+x)(1-x)=1-x^2=1-c;$$ this is a product of $$-1$$ and primes strictly less than $$c$$ (including $$2$$) and thus a quadratic residue (using that $$c\equiv 1\bmod 8$$), so $$(1+x)^{\frac{N+1}{2}}\in\mathbb F_N;$$ this implies that $$(1+x)^{\frac{N+1}{2}}=(1-x)^{\frac{N+1}{2}},$$ which gives that, if $$(1-x)^{\frac{N-1}{2}}=a+bx$$ with $$a,b\in\mathbb F_N$$, $$(a-bx)(1+x)=(a+bx)(1-x)\implies x(a-b)=x(b-a)\implies a=b.$$