Show that every prime $p>3$ is either of the form $6n+1$ or of the form $6n+5$

Question

Show that every prime $p>3$ is either of the form $6n+1$ or of the form $6n+5$, where $n=0,1,2, \dots$

Answer 1

Every integer is of the form $6n$ or $6n+1$ or $6n+2$ or $6n+3$ or $6n+4$ or $6n+5$ for some integer $n$. This is because when we divide an integer $m$ by $6$, we get a remainder of $0$, $1$, $2$, $3$, $4$, or $5$.

If an integer $m>2$ is of the form $6n$ or $6n+2$ or $6n+4$, then $m$ is even and greater than $2$, and therefore $m$ is not prime.

If an integer $m>3$ is of the form $6n+3$, then $m$ is divisible by $3$ and greater than $3$, and therefore $m$ is not prime.

We have shown that an integer $m>3$ of the form $6n$ or $6n+2$ or $6n+3$ or $6n+4$ cannot be prime. That leaves as the only candidates for primality greater than $3$ integers of the form $6n+1$ and $6n+5$.

Comment: In fact, it turns out that there are infinitely many primes of the form $6n+1$, and infinitely many primes of the form $6n+5$. Showing that there are infinitely many of the form $6n+5$ is quite easy, it is a small variant of the "Euclid" proof that there are infinitely many primes. Showing that there are infinitely many primes of the form $6n+1$ requires more machinery. But your question did not ask for such a proof.

Answer 2

$6$ divides $6n$, $2$ divides $6n+2$, $3$ divides $6n+3$, $2$ divides $6n+4$, and there are no other cases.

Answer 3

This is elementary algebra. For what value(s) of $n$ is $6n$ prime? $6n+2$? $6n+3$? $6n+4$? Are there any other possibilities besides these and the two that you already mentioned?

Answer 4

Copied from here.

Considering n = 6q + r

where q is a non-negative integer and the remainder r is one of 0, 1, 2, 3, 4, or 5.

• If the remainder is 0, 2 or 4, then the number n is divisible by 2, and can not be prime.
• If the remainder is 3, then the number n is divisible by 3, and can not be prime.

So if n is prime, then the remainder r is either

• 1 (and n = 6q + 1 is one more than a multiple of six), or
• 5 (and n = 6q + 5 = 6(q+1) - 1 is one less than a multiple of six).