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

Can we prove that every prime larger than $3$ gives a remainder of $1$ or $5$ if divided by $6$ and if so, which formulas can be used while proving?

-
You mean "gives a remainder of 1 or 5 if divided by 6". Note that every other remainder (0, 2, 3, or 4) implies that either 2 or 3 will divide the number, so it isn't prime. –  Henning Makholm Apr 16 at 16:19
I guess it is. But in book page, it is written like "1 and -1" –  A.D Apr 16 at 16:22

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$
-
Thank you! It is useful for me. –  A.D Apr 16 at 16:29
@A.D: You're welcome. –  barak manos Apr 16 at 16:29

HINT:

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

-
Thank you for hint! –  A.D Apr 16 at 16:31

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.$

-