Prime's rules

In fact, every prime $p>3$ satisfies this condition. Note that all such primes are of the form $p=6x\pm 1$ for some positive integer $x$ .

Squaring, we have $p^2=36x^2 \pm 12x + 1$ . We can rewrite this as $p^2=12(3x^2 \pm x)+1$ . Since $3x^2 \pm x$ is always even, it follows that $p^2=24k+1$ for some integer $k$ .