Proof for new deterministic primality test

Claim:

Let $p$ be a positive prime. Let $n \in \left\{1, 2, 3, ...\right\}$. Then $N = p\cdot 2^n+1$ is prime, if and only if it holds the congruence $3^{(N-1)/2} \equiv \pm1\ ($mod $N)$.

If the claim is true, we would have a fast deterministic test for numbers of the form $p\cdot2^n + 1$. That means, with small $p$ and large $n$, we could generate huge prime numbers, similar to Mersenne primes or Fermat primes.

A proof is needed. Thanks for Your attention.

• Criterion can not replaced by $3^{N-1}\equiv 1 ($mod $N)$ because there is a counter example. $N =356387⋅2^{11}+1=12289⋅59393$ while $3^{N−1}≡1($mod$N)$ – Guest_2015 Sep 12 '15 at 10:38
• Why downvote seems like Guest_2015 is chasing good leads here. – user76479 Sep 12 '15 at 10:45
• How do you generate primes fast? The test works for Mersenne primes and you are working modulo large $N$? – joro Sep 12 '15 at 12:01
• Now checking with the precise criterion, currently reached $n$ up to $14$ with first $3000$ primes (the $3000$th prime is $27449$). However this seems to be not much of an evidence in view of the above example with $p=356387$. – მამუკა ჯიბლაძე Sep 12 '15 at 12:21
• Modulo errors there are no counterexamples for $p \le 10^7, n \le 10^2$. – joro Sep 12 '15 at 12:54

@Igor Rivin

I will answer Your question here. I have done a research about safe primes, and I have found a new deterministic primality test for safe primes. This test goes as follows: We have two statements:

1.) Let $p=3$ (mod $4$) be prime. $2p+1$ is also prime if and only if $2p+1$ divides $2^p−1$.

2.) Let $p=1$ (mod $4$) be prime. $2p+1$ is also prime if and only if $2p+1$ divides $2^p+1$.

(Statement 1. is proven by Lagrange 1775, and statement 2. is proven by Batominovsky 2015)

So if a number $N=2\cdot p+1$ holds the congruence $2^p\equiv \pm1\ ($mod $N)$ then it is definitely prime.

From this point I went one step further to $N=p\cdot2^n + 1$.

I thought I could prove it in the case of a negative sign but I can only show that in this case, for fixed $n$, there can be only finitely many counterexamples. Nothing magical about $3$ by the way.

Let $p$ be prime and $n$ an integer such that $N=2^np + 1$ is such that, for some integer $a$ we have $a^{(N-1)/2} \equiv -1 \pmod N$. Then $N$ is prime or $p \le a^{2^{n-1}}/2^n$.

Proof: Let $m$ be the order of $a$ modulo $N$, then $m | 2^np$, so $m = 2^k$ or $2^kp$ for some $k \le n$. Since we have $-1$ in the congruence in the hypothesis, we conclude that $k=n$. If $m = 2^np$, then $N$ is prime ($\phi(N)=N-1$ iff $N$ is prime). The only other possibility is $m=2^n$. Assume that's the case. Then $2^n | \phi(N)$ but we cannot have $p|\phi(N)$ as that would force $\phi(N) \ge N-1$. So $(p,\phi(N))=1$ and the congruence $a^{(N-1)/2} \equiv -1 \pmod N$, then implies that $a^{2^{n-1}} \equiv -1 \pmod N$. So $N \le a^{2^{n-1}} + 1$ giving the result.

• There are counterexamples to primality with $a$ other than $3$. For instance $p=157,n=2,N=4p+1=629=17\cdot 37$ and $a=191$ satisfies $a^2 \equiv -1 \pmod N$. – Felipe Voloch Sep 13 '15 at 3:17
• So $a=3$ is special? – user76479 Sep 13 '15 at 4:42
• Maybe you want to exclude $a= -1$ or the congruence? – joro Sep 13 '15 at 6:07
• @joro The result is more interesting when you fix $n$ and vary $p$ than vice-versa. – Felipe Voloch Sep 13 '15 at 14:52
• When $a^{(N-1)/2}\equiv -1 \bmod N$, Felipe's observation that $2^n$ divides $\varphi(n)$ does imply that the number of non-Fermat prime divisors of $N$ is bounded for fixed $p$ and $n\rightarrow\infty$. – user80209 Sep 14 '15 at 2:45