Primality test for numbers of the form $2p+1$ Is this proof correct ?
Claim 

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

Proof
Suppose $q=2p+1$ is prime. $q \equiv 11 \pmod{12}$ so $3$ is quadratic residue module $q$
​and it follows that there is an integer $n$ such that $n^2 \equiv 3 \pmod{q}$ . This shows
$3^p=3^{(q-1)/2} \equiv n^{q-1}  \equiv 1 \pmod{q}$ showing $2p+1$ divides $3^p-1$ .
Conversely, let $2p+1$ be factor of $3^p-1$.
​Suppose that $2p+1$ is composite and let $q$ be its least prime factor.
Then $3^p \equiv 1 \pmod{q}$ and so we have $p=k \cdot \operatorname{ord_q(3)}$ for some integer $k$ .
​Since $p$ is prime there are two possibilities  $ \operatorname{ord_q(3)} =1 $   or  $ \operatorname{ord_q(3)} =p $  .
The first possibility cannot be true because $q$ is an odd prime number so $ \operatorname{ord_q(3)} =p $ .
On the other hand $\operatorname{ord_q(3)} \mid q-1$ , hence $p$ divides $q-1$ .
This shows $q>p$ and it follows $2p+1>q^2>p^2$
​which is contradiction since $p>3$ , hence $2p+1$ is prime .
Q.E.D.
 A: You could change the last sentence in your proof to:
This shows $q\ge p+1$, and it follows that $2p+1\ge q^2\ge(p+1)^2=p^2+2p+1$, which is a contradiction since $p\gt0$.  Hence $2p+1$ is prime.
A: The strict inequality $2p+1>q^2$ is not justified explicitly. I'd say that you have two options:


*

*Mention that $2p+1\equiv 3\pmod 4$, so $2p+1$ is not a square and the inequality is strict.

*Just write $2p+1\ge q^2$ instead.

A: Your proof is pretty much correct (the other answers have already mentioned how you could improve the last line), so let me give a somewhat easier proof of the second part. It only uses the Fermat-Euler theorem and some properties of the $\phi$ function.
Let $d$ be the smallest positive integer with:
$$3^d\equiv 1\pmod {2p+1}$$
If $2p+1\mid 3^p-1$, it follows that $d\mid p$ and thus $d=1$ or $d=p$, but $2p+1>2$ and hence $d=p$. This means that $p\mid\phi(2p+1)$ and since $\phi(2p+1),<2p+1$, we have $\phi(2p+1)=2p$ or $\phi(2p+1)=p$. In the second case we have $p\mid 2p+1$, which is impossible. It follows that $\phi(2p+1)=2p$ and therefore $2p+1$ is prime. 
