Let $ n \in \mathbb{N} $. Prove that if $n \not\equiv 1$ (mod $6$) and $n \not\equiv 5 $(mod $6$), then $n$ is not prime or $n = 2$ or $ n = 3$.

We can prove this using the contrapositive.

It is true when $ n = 1 $ and $n = 5$. As $ 1 \equiv 1 (mod 6)$ and $ 5 \equiv 5 (mod 6) $. Similarly, it is also true for 7 and 11. How can I prove it is true for all primes?


It seems simpler to just prove the statement by considering each case:

If $n \equiv 0\bmod 6 \Rightarrow n$ is not a prime

If $n \equiv 2\bmod 6 \Rightarrow n \equiv 0\bmod 2 \Rightarrow n$ is not a prime (we require $n \neq 2$)

If $n \equiv 3\bmod 6 \Rightarrow n\equiv 0\bmod 3 \Rightarrow n$ is not a prime (we require $n\neq 3$)

If $n \equiv 4\bmod 6 \Rightarrow n\equiv 0\bmod 2 \Rightarrow n$ is not a prime

Then we are done.


All primes greater then $3$ are neither divisble by $2$ nor by $3$. Hence, they must be of the form $6k+1$ or $6k-1$.

This is because the only possible residues modulo $6$ are $1$ and $5$, otherwise the number would be divisble by $2$ or by $3$ (or both)

  • $\begingroup$ Can it be proven that all primes greater than $3$ must be of the form $6k +1$ or $6k-1$. $\endgroup$ – u123435 Feb 25 '17 at 5:50
  • $\begingroup$ $6k+1 \equiv 1\bmod 6, 6k-1 \equiv 5\bmod 6$ Therefore the statement in the question is true $\leftrightarrow$ Peter's statement is true $\endgroup$ – mrnovice Feb 25 '17 at 16:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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