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?$

  • 3
    $\begingroup$ Do you know that there's a database of all pseudoprimes up to $2^{64}$ at cecm.sfu.ca/Pseudoprimes ? $\endgroup$ – Gerry Myerson Jul 22 '14 at 9:25
  • $\begingroup$ @Gerry Myerson: Yes, I know. But this is not a bottleneck. I can generate the $q$ primes and check the conditions, $2^{31}$ was only a limit for quick calculations because behind it I had to use multi-precision arithmetic. $\endgroup$ – gammatester Jul 22 '14 at 9:34
  • $\begingroup$ I wonder if there's anything to say about divisibility by $2q+1$ for prime $q$. Perhaps is there an interesting group of order $2q+1$ such as we have for $q^k-1$? $\endgroup$ – punctured dusk Jul 22 '14 at 11:02

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.

  • 1
    $\begingroup$ Thank you for the question and link to mathoverflow. Here $n$ should be replaced by $p$. $\endgroup$ – gammatester Mar 19 '18 at 9:11
  • $\begingroup$ @gammatester: done. Thanks for introducing the question, which had been puzzling me for weeks in that context (though not as long as you!). $\endgroup$ – fgrieu Mar 19 '18 at 9:38
  • $\begingroup$ Oh, I had missed that earlier equivalent proof by Daniel Fischer $\endgroup$ – fgrieu Mar 19 '18 at 14:48

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.