[SOLVED] Proof involving prime numbers

**Ryaη** · Sep 14th 2008, 10:35 AM

Prove that if p is a prime number and p does not equal 3, then 3 divides $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.

**o_O** · Sep 14th 2008, 10:50 AM

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

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

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

**Ryaη** · Sep 14th 2008, 12:34 PM

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

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

**o_O** · Sep 14th 2008, 01:18 PM

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

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

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

**Ryaη** · Sep 14th 2008, 01:44 PM

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 $2k$ is even and $2k+1$ is odd." What does the proof for either of those look like?

**Jhevon** · Sep 14th 2008, 01:49 PM

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 $2k$ is even and $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

**icemanfan** · Sep 14th 2008, 02:03 PM

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 $2k$ is even and $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.

Thread: [SOLVED] Proof involving prime numbers

LinkBack

Thread Tools

Display

[SOLVED] Proof involving prime numbers

Similar Math Help Forum Discussions

Proof involving a field and prime numbers

Series Involving Prime Numbers

Proof involving prime numbers

[SOLVED] Inequality proof involving natural numbers.

[SOLVED] Proof involving natural numbers

Search Tags