[LaurV]

Originally Posted by Dr Sardonicus

So if q = 2*k*p + 1 divides 2^p - 1, and k < 2*p + 2, then q is prime.

Respective k<6*p+1 when p=1 (mod 4)