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.

| cite | improve this question | | | | |
  • 6
    $\begingroup$ 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)$ $\endgroup$ – Guest_2015 Sep 12 '15 at 10:38
  • 4
    $\begingroup$ Why downvote seems like Guest_2015 is chasing good leads here. $\endgroup$ – user76479 Sep 12 '15 at 10:45
  • 2
    $\begingroup$ How do you generate primes fast? The test works for Mersenne primes and you are working modulo large $N$? $\endgroup$ – joro Sep 12 '15 at 12:01
  • 2
    $\begingroup$ 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$. $\endgroup$ – მამუკა ჯიბლაძე Sep 12 '15 at 12:21
  • 3
    $\begingroup$ Modulo errors there are no counterexamples for $p \le 10^7, n \le 10^2$. $\endgroup$ – 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$.

| cite | improve this answer | | | | |

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.

| cite | improve this answer | | | | |
  • 1
    $\begingroup$ 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$. $\endgroup$ – Felipe Voloch Sep 13 '15 at 3:17
  • $\begingroup$ So $a=3$ is special? $\endgroup$ – user76479 Sep 13 '15 at 4:42
  • $\begingroup$ Maybe you want to exclude $a= -1$ or the congruence? $\endgroup$ – joro Sep 13 '15 at 6:07
  • 3
    $\begingroup$ @joro The result is more interesting when you fix $n$ and vary $p$ than vice-versa. $\endgroup$ – Felipe Voloch Sep 13 '15 at 14:52
  • 1
    $\begingroup$ 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$. $\endgroup$ – user80209 Sep 14 '15 at 2:45

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.