Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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

3 Answers 3

up vote 8 down vote accepted


  • $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$
share|improve this answer
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


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

share|improve this answer
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.$

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.