4
$\begingroup$

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?
$\endgroup$
  • $\begingroup$ en.wikipedia.org/wiki/Carmichael_number $\endgroup$ – Peđa Terzić Aug 26 '15 at 8:19
  • $\begingroup$ @MathBot you have to find a Carmichael number of form $N=p\cdot 2^n+1$. Carmichael numbers have at least three distinct prime factors, say $q_1, q_2, q_3$ and have $q_i-1|N-1=p\cdot 2^n$. This is somewhat restrictive. The condition on the prime $3$ alone is far weaker than the Carmichael condition. $\endgroup$ – Mark Bennet Aug 26 '15 at 8:25
  • $\begingroup$ Some related theorems for the variant... $\endgroup$ – Raymond Manzoni Aug 26 '15 at 16:52
6
$\begingroup$

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.
$\endgroup$
1
$\begingroup$

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

$\endgroup$

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.