Thread: [SOLVED] Proof involving prime numbers

Prove that if p is a prime number and p does not equal 3, then 3 divides $\displaystyle p^2 + 2$. I'm given a hint that says, "When p is divided by 3, the remainder is either 0, 1, or 2. That is, for some integer k, p=3k or p=3k+1 or p=3k+2. I understand the hint and the initial statement, I just don't know where to start.

First off, $\displaystyle p \neq 3k$ since that would mean p is divisible by something other than 1 and itself and we already said $\displaystyle p \neq 3$

So just go through the other two cases:
If $\displaystyle p = 3k + 1$ then $\displaystyle p^2 + 2 = (3k+1)^2 + 2 = 9k^2 + 6k + 3 = 3(3k^2 + 2k + 1) \ \Rightarrow \ 3 \mid (p^2 + 2)$

If $\displaystyle p = 3k + 2$ then ........... Finish it off.

That's where I got to, but I didn't think that was proof of the statement.

Why does $\displaystyle 3(3k^2 + 2k + 1) \ \Rightarrow \ 3 \mid (p^2 + 2)$?

By definition, $\displaystyle 3 \mid (p^2 + 2) $ iff there exists an integer $\displaystyle c$ such that $\displaystyle 3c = p^2 + 2$.

From our work, we can see that $\displaystyle c = 3k^2 + 2k + 1$

Or in layman terms, we have 3 times something equal to $\displaystyle p^2 + 2$. So obviously, 3 and that something iare a factor of it, i.e. 3 and that something divide $\displaystyle p^2 + 2$.

Gotcha. Thanks for the help. I have one more question that is somewhat on topic.

We are proving things in class but only in the sense that we have to take the work someone else has done and assume it's true. At some point in a proof do you just have to use common sense. For example, "Let k be an integer. Then $\displaystyle 2k$ is even and $\displaystyle 2k+1$ is odd." What does the proof for either of those look like?

Originally Posted by Ryaη

Gotcha. Thanks for the help. I have one more question that is somewhat on topic.

We are proving things in class but only in the sense that we have to take the work someone else has done and assume it's true. At some point in a proof do you just have to use common sense. For example, "Let k be an integer. Then $\displaystyle 2k$ is even and $\displaystyle 2k+1$ is odd." What does the proof for either of those look like?

it is a definition. even numbers are those that are divisible by 2 and odd numbers are those that are not (meaning, when we divide them by 2, we have a remainder of 1). and the definitions follow immediately

Originally Posted by Ryaη

Gotcha. Thanks for the help. I have one more question that is somewhat on topic.

We are proving things in class but only in the sense that we have to take the work someone else has done and assume it's true. At some point in a proof do you just have to use common sense. For example, "Let k be an integer. Then $\displaystyle 2k$ is even and $\displaystyle 2k+1$ is odd." What does the proof for either of those look like?

As Jhevon has already pointed out, those facts follow from the definition of even and odd. Sometimes you will have to use axioms (e.g. two parallel lines never intersect), but that's about as close to "common sense" as a proof can get.