# On a result of Euler on pseudoprimes

In several sources (for instance on page 58 of the first ed. of Crandall & Pomerance book on prime numbers or at the end of this paper by J. H. Jaroma), I have seen a result that goes like this:

Let $$p$$ be an odd prime congruent to $$-1$$ modulo $$4$$. Then $$2p+1$$ is a prime iff $$(2p+1) \mid (2^{2p}-1)$$.

Do you know if the hypothesis $$p \equiv -1 \pmod 4$$ may be removed? If the result is still valid for primes congruent to $$1$$ modulo $$4$$, I wonder why it is that it is not mentioned in the sources I referred to above...

• This post on Mathematics seems related: Proving $2p +1 \mid 2^p + 1$. Feb 13, 2021 at 13:27
• Thanks, Martin... The result there allows us to prove this: if p is congruent to 1 mod. 4 and $2p+1$ is a prime then 2p+1 divides $2^{2p}-1$. Feb 13, 2021 at 13:37
• Hmm, thus this is true for all primes including the even prime (p=2). Jul 14, 2021 at 7:26

Yes, the result holds for every odd prime number $$p$$... I certainly find it somewhat "strange" that it is only stated for primes congruent to $$-1$$ modulo $$4$$ in several places:
Proposition. Let us suppose that $$p$$ is an odd prime number and that $$2p+1$$ divides $$2^{2p}-1$$. Then, $$2p+1$$ is a prime number.
Proof. (I learnt it from J. I. Restrepo) For the sake of contradiction, let us suppose that $$2p+1$$ is not a prime number and that $$q$$ is a prime number dividing $$2p+1$$. From the hypothesis and Fermat's little theorem we have that
$$\begin{eqnarray} 2^{2p} \equiv 1 \pmod{q}\\ 2^{q-1} \equiv 1 \pmod{q}. \end{eqnarray}$$
It follows from these congruences that $$\mathrm{ord}_{q}(2)=:\mathfrak{o}$$ is a common positive divisor of $$2p$$ and $$q-1$$; since there are only four positive divisors of $$2p$$ and $$q-1 \leq (p-\frac{1}{2}), we get that $$\mathfrak{o}=1$$ or $$\mathfrak{o}=2$$. Given that $$q$$ is a prime number, $$\mathfrak{o}$$ can't be equal to $$1$$. Hence, $$\mathfrak{o}=2$$ and $$q=3$$.
From what we have established in the above paragraph, we obtain that $$2p+1=3^{\ell}$$ for some $$\ell \in \mathbb{Z}^{+} \setminus \{1\}$$. This implies that $$9 \mid (2^{2p}-1)$$ which is an absurdity because $$9 \mid (2^{n}-1)$$ iff $$6 \mid n$$. Q.E.D.