Prove that every prime larger than $3$ gives a remainder of $1$ or $5$ if divided by $6$

Solution 1:

HINT:

Every positive integer can be written as $$6n,6n\pm1,6n\pm2=2(3n\pm1),6n+3=3(2n+1)$$

Solution 2:

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$

Solution 3:

Hint $ $ By Euclid $\ (n,\,6) = (n\ {\rm mod}\ 6,\,6).\,$ Yours is special case $\,(n,6)=1,\,$ e.g. prime $\,n>3.$

So integers coprime to $\,6\,$ have residues (mod $6)\,$ that are coprime to $\,6,\,$ i.e. $\,1$ or $\,5\pmod{\! 6}.$

Thus the above is a special case of the fact that the gcd remains unchanged upon applying a single descent step of the Euclidean algorithm for the gcd (proved in the prior linked post).