Prime equals Plus or Minus One modulo 6

Theorem

Let $p$ be a prime number greater than $3$.

Then $p$ is either of the form:

$p = 6 n + 1$

or:

$p = 6 n - 1$

That is:

$p = \pm 1 \pmod 6$

To demonstrate that there are prime numbers of either form, note:

$5 = 6 \times 1 - 1$

$7 = 6 \times 1 + 1$

The only other possibilities for $p$ are:

$p = 6 n$, in which case $6 \divides p$ and so $p$ is not prime

$p = 6 n + 2$, in which case $2 \divides p$ and so $p$ is not prime

$p = 6 n + 3$, in which case $3 \divides p$ and so $p$ is not prime

$p = 6 n + 4$, in which case $2 \divides p$ and so $p$ is not prime

$p = 6 n + 5$, which is the same as $p = 6 \paren {n + 1} - 1$, which is covered above.

Hence the result.

$\blacksquare$