Theorem 1 (Lucas)   $M_p$ is prime if and only if $\alpha^{(M_p+1)/2}\equiv -1\pod{M_p}$ , where $\alpha = 2+\sqrt{3}$ .

Lemma 2   If $p>3$ is prime, then $\alpha^{p-1}\equiv 1\pod p$ or $\alpha^{p+1}\equiv 1\pod p$ .

Proof.

where $\Leg{\cdot}{\cdot}$ is the Legendre symbol. Thus

Lemma 3   Let $p$ be a prime with $p\equiv 7\pod 8$ and $p\equiv 7\pod {12}$ . Then $\alpha^{(p+1)/2}\equiv -1\pod p$ .

Proof. $(1+\sqrt{3})^2 = 4+2\sqrt{3} = 2\alpha$ , so that $$ (1+\sqrt{3})^{p+1} = 2^{(p+1)/2}\alpha^{(p+1)/2} $$ But $p\equiv 7\pod 8$ , so that $\Leg{2}{p}=1$ . Thus $2^{(p+1)/2} \equiv 2\cdot 2^{(p-1)/2} \equiv 2 \pod p$ and therefore $$ (1+\sqrt{3})^{p+1} \equiv 2\alpha^{(p+1)/2}\pod p $$ Also, $$ (1+\sqrt{3})^{p+1} = (1+\sqrt{3})(1+\sqrt{3})^p \equiv (1+\sqrt{3})(1+3^{(p-1)/2}\sqrt{3})\pod p $$ But $p\equiv 7\pod {12}$ , so $3^{(p-1)/2}\equiv -1\pod p$ and thus $$ (1+\sqrt{3})^{p+1} \equiv (1+\sqrt{3})(1-\sqrt{3}) = -2\pod p $$ Putting together the two expressions for $(1+\sqrt{3})^{p+1}$ , we get $\alpha^{(p+1)/2}\equiv -1\pod p$ .

Proof. $(\Rightarrow):$ If $M_p$ is prime where $p>3$ is prime, then note that $M_p\equiv 7\pod 8, 7\pod 12$ so that $M_p$ satisfies the conditions of Lemma 3. The result follows.

$(\Leftarrow):$ If $\alpha^{(M_p+1)/2} \equiv -1\pod{M_p}$ , choose $q\mid M_p$ for $q$ a prime. Since $M_p\equiv 7\pod 12$ , we have $q>3$ . Since $\alpha^{(M_p+1)/2}\equiv -1\pod{M_p}$ also $\alpha^{(M_p+1)/2}\equiv -1\pod q$ and thus $\alpha^{M_p+1}\equiv 1\pod q$ . But $M_p+1=2^p$ , so $$ \alpha^{2^p} \equiv 1\pod q $$ Thus the order of $\alpha\pod q$ divides $2^n$ . It can't divide $2^{n-1}$ since $\alpha^{(M_p+1)/2} \equiv -1\pod q$ , so its order is precisely $2^n = M_p+1$ . However, $\alpha^{q+1}\equiv 1\pod q$ or $\alpha^{q-1}\equiv 1\pod q$ by Lemma 2 and thus $q\geq M_p$ . But $q\mid M_p$ , so $q=M_p$ and $M_p$ is in fact prime.