New deterministic primality test for numbers of the form $p\cdot 2^n + 1$

Question

Edit: Sorry, there was an error.

Old Claim (not true because there is a counter-example):

Let $p$ be 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} \equiv 1\ ($mod $N)$.

The right claim goes as follows

Let $p$ be 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.

There are a lot of questions:

• Is a proof possible?
• If yes, can the expression $3^{(N-1)/2}$ faster evaluated than Mersenne test?
• Computing $3^{(N-1)/2}$: Are there faster methods than binary modular exponentiation?

Answer 1

Counterexample : $N=356387\cdot 2^{11}+1=12289\cdot 59393\;$ while $\;3^{N-1}\equiv 1\pmod{N}$

It is interesting to observe

• $\;2^{N-1}\not\equiv 1\pmod{N}\;$
• $\;12289=3\cdot 2^{12}+1\;$ while $\;59393=29\cdot 2^{11}+1\;$ so that both prime factors are (minimal)
  $2^n$ safe-primes : OEIS A051900.

Answer 2

Modified claim (Euler pseudoprime to base $3$)

Consider $\,N =p\cdot 2^n+1\,$ with $p$ an odd prime and $n$ a positive integer then according to

Euler's criterion we have for $N$ an odd prime and $a$ coprime to $N$ : $$a^{(N-1)/2} \equiv \left(a\over N\right)\pmod{N}$$

with the Legendre symbol at the right side $\pm 1$ as claimed in our case $a=3$.

The converse is not so easy but a good start may be Lucas' theorem strengthened by Kraitchik and Lehmer (from The Prime Pages) :

Let $N>1$. If for every prime factor $q\,$ of $\;N-1$ there is an integer $a$ such that

• $\displaystyle a^{N-1}\equiv 1\pmod{N},\quad$ and
• $\displaystyle a^{(N-1)/q}\not\equiv 1\pmod{N}$

then $\; N$ is prime.

The only prime factors $q$ of $\,N-1\,$ are $2$ and $p$. If we restrict ourself to evaluation of powers of $a=3$ we get :

if

• $\;\displaystyle 3^{(N-1)/2}\equiv -1\pmod{N}\;$ (implying $\;3^{N-1}\equiv 1\pmod{N}$)$\quad$ and
• $\;\displaystyle 3^{(N-1)/p}\not\equiv 1\pmod{N}\;$

then $N$ is prime.

Note that computations are quite efficient here since $\;(N-1)/p=2^n$ so that we could evaluate $\;r:=3^{\large{2^{n-1}}}\pmod{N}$ by squaring only and then compute $\;r^p\pmod{N}$ for the first test and $\;r^2\pmod{N}$ for the second.

This is of course weaker than your claim with the important drawback of excluding $\;\displaystyle 3^{(N-1)/2}\equiv 1\pmod{N}\;$ when $3$ is a quadratic residue modulo $N$ : that is approximately half of the interesting cases for "not too large" values of $N$! (and the minor inconvenient of adding a second test...)

A closer look shows however that $3$ will be a quadratic residue modulo $N$ only if $n=1$ or $p=3$
(I think from this result of the quadratic residue theory : $\left(3\over N\right)=+1\;$ iff $\;N\equiv \pm 1\pmod{12}\;$ without verifying all the cases I'll admit...).
The previous conditions should thus apply for all the primes $\,N =p\cdot 2^n+1\,$ with $p$ prime $>3\;$ and $n>1$.

The remaining case of prime $\,N =2\,p+1\,$ ("safe prime") was studied by Sophie Germain while the prime $\,N =3\cdot 2^n+1\,$ OEIS A039687 was studied by Golomb.

This result is incomplete but should be at least a start...

Answer 3

First off, this question was cross-posted to MO without a disclaimer.

I've just answered this question negatively there. A counterexample to "the right claim" is given by $N=2197475332227227631617$ and it's just the smallest one from the list of 659 counterexamples that I've found.