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)
