3
$\begingroup$

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]$ .

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

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.$$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.