Fermat pseudoprimes p to base 2 (AKA Sarrus or Poulet numbers) with special properties Are there any known Fermat pseudoprimes $p\;$ to base $2\;$ (Sarrus or Poulet numbers) with the properties
$q = (p-1)/2\;$ is prime and $p \equiv 0 \pmod 3?$
I was not able to find any example up to $p = 2^{31}-1.$ Is there an argument that they cannot exist?
This question is related to Fast check of safe primes or Sophie Germain primes where I added the condition $p \not \equiv 0 \pmod 3?$
 A: No, there can't be Fermat pseudoprimes $p$ to base $2$ with $(p-1)/2$ prime. Proof, detailing Fedor Petrov's answer:
Assume $p=2q+1$ with $q$ prime and $2^{p-1}\equiv1\pmod p$.
For all $x$ coprime with $p$, it holds that $x^{\varphi(p)}\equiv1\pmod p$, where $\varphi$ is Euler's totient function. $p$ is odd, thus holds for $x=2$. Thus $2^{\varphi(p)}\equiv1\pmod p$.
Let $d=\gcd(\varphi(p),p-1)$. By Bézout's lemma, $d=a\;\varphi(p)+b(p-1)$ for some $(a,b)\in\Bbb Z^2$. Therefore, and given that $2$ is coprime with $p$
$$\begin{align}2^d&\equiv2^{a\;\varphi(p)+b(p-1)}&\pmod p\\
&\equiv{(2^{\varphi(p)})}^a\;{(2^{p-1})}^b&\pmod p\\
&\equiv1^a\;1^b&\pmod p\\
&\equiv1&\pmod p
\end{align}$$
$p$ is odd, thus both $\varphi(p)$ and $p-1$ are even. $d$ divides both, thus is even. $p-1=2q$ with $q$ prime, thus an even $d$ dividing $p-1$ is either $2$ or $p-1$. With $2^d\equiv1\pmod p$, $d=2$ would imply that $p$ divides $3$, which can't hold for $p=2q+1$ with $q$ prime. Therefore, $d=p-1$.
Therefore, $p-1$ divides $\varphi(p)$. Therefore, $p$ is prime.
Note: we did not need to invoke the question's $p\equiv 0\pmod3$ or the Pocklington criterion.
