Prove that every prime larger than $3$ gives a remainder of $1$ or $5$ if divided by $6$
HINT:
Every positive integer can be written as $$6n,6n\pm1,6n\pm2=2(3n\pm1),6n+3=3(2n+1)$$
Yes:
- $N \equiv 0 \pmod 6 \implies N$ is divisible by $6 \implies$ $N$ is not a prime
- $N \equiv 2 \pmod 6 \implies N$ is divisible by $2 \implies$ $N$ is not a prime (or $N=2$)
- $N \equiv 3 \pmod 6 \implies N$ is divisible by $3 \implies$ $N$ is not a prime (or $N=3$)
- $N \equiv 4 \pmod 6 \implies N$ is divisible by $2$ and $N\geq4 \implies$ $N$ is not a prime
- $N$ is a prime larger than $3 \implies N \not\equiv 0,2,3,4 \pmod 6 \implies N \equiv 1,5 \pmod 6$