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$