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.
Best Answer
@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:
(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$.