2
$\begingroup$

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.

  • 0
    Tha$n$k 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.2012-09-26

4 Answers 4

8

Hint: all prime numbers greater than 2 are odd.

  • 0
    (+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).2012-09-26
3

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

1

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

1

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!