Results 1 to 7 of 7

Math Help - [SOLVED] Proof involving prime numbers

  1. #1
    Junior Member
    Joined
    Sep 2008
    From
    Indiana
    Posts
    26

    [SOLVED] Proof involving prime numbers

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Sep 2008
    From
    Indiana
    Posts
    26
    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)?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Sep 2008
    From
    Indiana
    Posts
    26
    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?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by Ryaη View Post
    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
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Apr 2008
    Posts
    1,092
    Quote Originally Posted by Ryaη View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof involving a field and prime numbers
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: March 17th 2012, 03:40 PM
  2. Series Involving Prime Numbers
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: September 5th 2011, 01:14 PM
  3. Proof involving prime numbers
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: March 7th 2011, 02:38 PM
  4. [SOLVED] Inequality proof involving natural numbers.
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 13th 2009, 08:19 AM
  5. [SOLVED] Proof involving natural numbers
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 12th 2009, 09:20 PM

Search Tags


/mathhelpforum @mathhelpforum