Modular Arithmetic and Primes

Let $n \in \mathbb{N}$. Prove that if $n \not\equiv 1$ (mod $6$) and $n \not\equiv 5$(mod $6$), then $n$ is not prime or $n = 2$ or $n = 3$.

We can prove this using the contrapositive.

It is true when $n = 1$ and $n = 5$. As $1 \equiv 1 (mod 6)$ and $5 \equiv 5 (mod 6)$. Similarly, it is also true for 7 and 11. How can I prove it is true for all primes?

It seems simpler to just prove the statement by considering each case:

If $n \equiv 0\bmod 6 \Rightarrow n$ is not a prime

If $n \equiv 2\bmod 6 \Rightarrow n \equiv 0\bmod 2 \Rightarrow n$ is not a prime (we require $n \neq 2$)

If $n \equiv 3\bmod 6 \Rightarrow n\equiv 0\bmod 3 \Rightarrow n$ is not a prime (we require $n\neq 3$)

If $n \equiv 4\bmod 6 \Rightarrow n\equiv 0\bmod 2 \Rightarrow n$ is not a prime

Then we are done.

All primes greater then $3$ are neither divisble by $2$ nor by $3$. Hence, they must be of the form $6k+1$ or $6k-1$.

This is because the only possible residues modulo $6$ are $1$ and $5$, otherwise the number would be divisble by $2$ or by $3$ (or both)

• Can it be proven that all primes greater than $3$ must be of the form $6k +1$ or $6k-1$. – u123435 Feb 25 '17 at 5:50
• $6k+1 \equiv 1\bmod 6, 6k-1 \equiv 5\bmod 6$ Therefore the statement in the question is true $\leftrightarrow$ Peter's statement is true – mrnovice Feb 25 '17 at 16:50