Do $2^{n-1}\equiv1\pmod n$ and $(n-1)/2$ prime imply $n$ prime?

Equivalently: Does $n$ being a Fermat pseudoprimes to base 2 (OEIS A001567) imply that $(n-1)/2$ is composite? That holds for all $n<2^{64}$, based on Jan Feitsma's table.

Motivation is a simplification in the search of safe primes as used in cryptography.

Progress so far: Pocklington's theorem states that if $q>\sqrt n-1$ is a prime dividing $n-1$, and $a^{n-1}\equiv1\pmod n$, then $n$ is prime or $\gcd(a^{(n-1)/q},n)\ne1$. Applying this for $a=2$, it comes that any counterexample $n$ to the propositions would be a multiple of $3$.

The question then boils down to: do $6k+1$ prime imply $4^{6k+1}\not\equiv1\pmod{4k+1}$ ?


We have $2^{\varphi(n)}\equiv 1 \pmod n$, thus $2^k\equiv 1$, where $k=\text{gcd}(\varphi(n),n-1)$. Note that $k$ is even, since both $n-1$ and $\varphi(n)$ are even. If $n=2p+1$ for prime $p=(n-1)/2$, then even divisor of $n-1$ is either 2 or $2p$. If $k=2$, we get $n|2^2-1=3$; if $k=2p=n-1$, we get $\varphi(n)\geqslant n-1$, thus $n$ is prime.

  • $\begingroup$ Introducing $\varphi(n)$ was nice! I made a detailed version there. $\endgroup$ – fgrieu Mar 18 '18 at 20:36

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.