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.

I am having a hard time understanding this question. I have never had any number theory and so I am lost on how to start this proof. The question is as follows.

Prove that every prime $p$ greater than $2$ satisfies $p \bmod 8 = r$, where $r$ is $1, 3, 5$, or $7$.

Any help would be greatly appreciated. Thanks.

share|improve this question
Welcome to math.se Karol. One way to approach this problem is with a mathematicians best friend, the contrapositive. The contrapositive of the proposition "P, therefore Q" is the equivalent proposition "Not Q, therefore not P". For example, if I asked you to show that if $n^2$ is even, then $n$ must be even, it may be hard. It's contrapositive is "If n is odd (not even), then $n^2$ is odd (not even)" which is more easily seen to be true. Here, you can try showing this instead: If $p$ is an integer greater than 2 with $p \equiv 0,2,4,6 \mod 8$, then $p$ is not prime." –  Ragib Zaman Sep 26 '12 at 4:08
Thank you for your suggestion. I am afraid I do not understand it. I have never worked with mod's before or number theory problems.I do not quite understand what this means. –  Karol Sep 26 '12 at 5:24
add comment

4 Answers 4

Hint: all prime numbers greater than 2 are odd.

share|improve this answer
(+1): I think you should note, though, that your hint is in fact equivalent to the statement to be proved (though arguably simpler to prove and intuitively grasp for a beginner). –  Cameron Buie Sep 26 '12 at 4:18
add comment

Hint $\ $ Consider the more familiar fact that a prime $\neq 2,5$ has decimal units digit one of $\,1,3,7,9$. Note that the other digits are excluded since they yield obvious proper factors, e.g. $\rm\:5\:|\:10\,n+5.$

share|improve this answer
add comment

From your comment, I take it that you're having difficulty figuring out what "$p\pmod 8=r$" means. One definition is that $p\pmod 8=1$, for example represents all the numbers of the form $p=8k+1$, for any integer $k$. In other words, we're talking about the set of numbers $\{\dots -15, -7, 1, 9, \dots\}$ (where the $k$ values in this case are $k=-2, -1, 0, 1$). Note that in the sequence $-15, -7, 1, 9$, all adjacent terms differ by 8, since they'll all have the same remainder when divided by 8.

Continuing this for your example, we have $$ \begin{align} p\pmod 8 = 1\text{ says that p is among } &\dots-15, -7, 1, 9, 17,\dots\\ p\pmod 8 = 3\text{ says that p is among } &\dots-13, -5, 3, 11, 19,\dots\\ p\pmod 8 = 5\text{ says that p is among } &\dots-11, -3, 5, 13, 21,\dots\\ p\pmod 8 = 7\text{ says that p is among } &\dots-9, -1, 7, 15, 23,\dots\\ \end{align} $$ In other words, saying that $p\pmod 8=1, 3, 5, 7$ is exactly the same as saying that $p$ is an odd number and that's certainly true for any prime $p\ne 2$.

Test your understanding: convince yourself that any odd number $n$ we'll have $n\pmod 4=1\text{ or }3$.

share|improve this answer
add comment

Hmm, first, $\bmod{}$ means remainder after division.
$$7 \bmod 3 = 1 \\ 19 \bmod 8 = 3$$

Got the idea?

Now, if $n \bmod 8$ were $2$, $4$ or $6$, then that number is divisible by $2$. Hence not prime!

share|improve this answer
add comment

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.