# Proving that every prime $p > 2$ satisfies $p \bmod 8 = r$ for some $r\in \{1,3,5,7\}$

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.

-
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

Hint: all prime numbers greater than 2 are odd.

-
(+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

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

-

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

-

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!

-