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](https://oeis.org/A001567)) imply that $(n-1)/2$ is composite? That holds for all $n<2^{64}$, based on [Jan Feitsma's table](http://www.cecm.sfu.ca/Pseudoprimes/).


Motivation is a simplification in the search of [safe primes](https://en.wikipedia.org/wiki/Safe_prime) as used in cryptography.




---


Progress so far: [Pocklington's theorem](https://en.wikipedia.org/wiki/Pocklington_primality_test#Pocklington_criterion) 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}$ ?



Do $2^{n-1}\equiv1\pmod n$ and $(n-1)/2$ prime imply $n$ prime?
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.


