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.

|cite|improve this question
$\endgroup$
  • 3
    $\begingroup$ 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." $\endgroup$ – Ragib Zaman Sep 26 '12 at 4:08
  • $\begingroup$ 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. $\endgroup$ – Karol Sep 26 '12 at 5:24
8
$\begingroup$

Hint: all prime numbers greater than 2 are odd.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ (+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). $\endgroup$ – Cameron Buie Sep 26 '12 at 4:18
3
$\begingroup$

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

|cite|improve this answer
$\endgroup$
1
$\begingroup$

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

|cite|improve this answer
$\endgroup$
1
$\begingroup$

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!

|cite|improve this answer
$\endgroup$

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.