27
$\begingroup$

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.

Improve this question
$\endgroup$
17
  • 7
    $\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
    Commented Sep 12, 2015 at 10:38
  • 4
    $\begingroup$ Why downvote seems like Guest_2015 is chasing good leads here. $\endgroup$
    – user76479
    Commented Sep 12, 2015 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
    Commented Sep 12, 2015 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$
    – მამუკა ჯიბლაძე
    Commented Sep 12, 2015 at 12:21
  • 3
    $\begingroup$ Modulo errors there are no counterexamples for $p \le 10^7, n \le 10^2$. $\endgroup$
    – joro
    Commented Sep 12, 2015 at 12:54

3 Answers 3

Reset to default
30
$\begingroup$

The claim does not hold. A counterexample is given by $n=14$, $p=134123250258009499$ and correspondingly $$N = 2197475332227227631617 = 193 \cdot 12289 \cdot 926510094425921.$$ It can be easily verified that $$3^{(N-1)/2} \equiv 1 \pmod{N},$$ but $N$ is not prime.

A couple more values of $N$ giving counterexamples: $$300334937065845770469377,\ 80203520301265852381167617.$$

ADDED. Here is a list of 659 counterexamples that I composed from the known prime factors of generalized Fermat numbers GFN(3).

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ How did you guess? $\endgroup$
    – Turbo
    Commented Apr 1, 2023 at 3:16
  • 5
    $\begingroup$ @Turbo: I composed them from known prime factors of generalized Fermat numbers $3^{2^k}+1$. $\endgroup$
    – Max Alekseyev
    Commented Apr 1, 2023 at 3:20
12
$\begingroup$

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

Improve this answer
$\endgroup$
6
$\begingroup$

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .