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

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.
• Introducing $\varphi(n)$ was nice! I made a detailed version there. – fgrieu Mar 18 '18 at 20:36