5
$\begingroup$

In 1750 Euler stated following theorem :

Let $p \equiv 3 \pmod 4$ be prime then $2p+1$ is prime iff $2p+1 \mid 2^p-1$ .

In 1775 Lagrange gave a proof of the theorem .

Recently I have formulated following claim :

Let $p \equiv 5 \pmod 6$ be prime then $2p+1$ is prime iff $2p+1 \mid 3^p-1$ .

Is this statement known ?

P.S.

You can find my proof attempt here .

$\endgroup$

1 Answer 1

8
$\begingroup$

The if-part is a special case of Pocklingtons theorem (see https://en.wikipedia.org/wiki/Pocklington_primality_test ). The only if part requires some computation, as you need a quadratic non-reside mod 2p+1. As far as I know in general there is no reasonable algorithm for finding a non-residue is known, which is why you need some congruential restriction. However, in practice you would pick integers at random and check them, which takes on average two tests. Moreover, if you just check integers $1,2,3\ldots$, then after $\mathcal{O}(\log^2)$ tests you either obtain a non-residue, or a disproof of GRH.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.