Results 1 to 7 of 7

Math Help - elem. numbr theory - prove P

  1. #1
    Member cassiopeia1289's Avatar
    Joined
    Aug 2007
    From
    chicago
    Posts
    101

    elem. numbr theory - prove P

    OK: prove "If n is an odd integer, then there exists an integer x such that n = 4x + 1 or n = 4x + 3.

    I could also prove its negation, which is: For some integer x such that n is odd and for all integer x, n doesn't equal 4x + 1 and n doesn't equal 4x + 3.

    So I start off with: Let n = 2k + 1 for some integer k.
    Then I'm stuck ... lol

    (I wanna prove the first, because I feel as though it would be easier) - but how do I show 2k + 1 = 4x + 1 or 4x + 3???
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,

    For that, I would do a direct proof o.O

    If n is odd, okay, it is odd.

    Now, a number can be written in 4 ways :
    4x
    4x+1
    4x+2
    4x+3

    Which of those are indeed odd ??
    You're thus proving that if n is odd, then there's only ... ways it can be written.
    Last edited by Moo; September 5th 2008 at 09:23 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member Aryth's Avatar
    Joined
    Feb 2007
    From
    USA
    Posts
    651
    Thanks
    1
    Awards
    1
    To expand on it, you basically have to prove that 4x + 1 and 4x + 3 are, in fact odd.

    For the first option: 4x

    If k = 2x, then:

    4x = 2k, which is even.

    For the second option: 4x + 1

    If k = 2x, then:

    4x + 1 = 2k + 1, which is odd

    For the third option: 4x + 2

    First:

    4x + 2 = 2(2x + 1)

    Now, if k = 2x + 1, then

    4x + 2 = 2k, which is even

    For the last option: 4x + 3

    First:

    4x + 3 = (4x + 2) + 1 = (2(2x + 1)) + 1

    If k = 2x + 1, then

    4x + 3 = 2k + 1

    And you can easily see that only 4x + 1 and 4x + 3 are odd.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member cassiopeia1289's Avatar
    Joined
    Aug 2007
    From
    chicago
    Posts
    101
    ok, but why would you have to bring in 4x and 4x + 2 - the problem doesn't mention those and they're obviously going to be even. so why even bring them in?

    so I tried working it:
    Let n = 2k + 1 for some integer k.
    So 2k + 1 = 4x + 3
    2k = 4x + 2
    2k = 2(2x + 1)
    k = 2x + 1

    thus they're the same ... ???
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member Aryth's Avatar
    Joined
    Feb 2007
    From
    USA
    Posts
    651
    Thanks
    1
    Awards
    1
    Quote Originally Posted by cassiopeia1289 View Post
    huh? you lost me:

    so I tried working it:
    Let n = 2k + 1 for some integer k.
    So 2k + 1 = 4x + 3
    2k = 4x + 2
    2k = 2(2x + 1)
    k = 2x + 1

    thus they're the same ... ???
    If you're going to do it that way, you have to do something different:

    Let n = 2k + 1 for some integer k.
    So n = 4x + 3 for some integer x
    n = (4x + 2) + 1
    n = 2(2x + 1) + 1
    Now, if you let k = 2x + 1, then
    n = 2k + 1
    Thus for some integer x, 4x + 3 yields an odd integer n.
    Last edited by Aryth; September 5th 2008 at 09:27 AM. Reason: Changed m to k to avoid confusion
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member cassiopeia1289's Avatar
    Joined
    Aug 2007
    From
    chicago
    Posts
    101
    ok, I get it.
    so how would you conclude it: therefore, the odd integer n does equal 4x+3.

    it just looks really disorganized and a bit confusing, but I'm pretty sure I understand it.
    Last edited by cassiopeia1289; September 5th 2008 at 09:50 AM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member Aryth's Avatar
    Joined
    Feb 2007
    From
    USA
    Posts
    651
    Thanks
    1
    Awards
    1
    What you do is:

    1. State the assertion and any other information:

    If n is an odd integer, then there exists an integer x such that n = 4x + 1 or n = 4x + 3.

    n is odd, therefore n = 2k + 1

    2. Separate this into cases:

    Case 1: There exists an integer x such that n = 4x + 1

    Case 2: There exists an integer x such that n = 4x + 3

    3. Prove each case directly:

    Case 1:

    If n is odd, then n = 2k + 1.

    To prove this, we have to show that n = 4x + 1 is also an odd integer. We want to go from n = 4x + 1 to n = 2k + 1, then we have proved that there is at least one (more than likely all) x that causes n to be odd.

    So, we start with our assumption:

    n = 4x + 1

    Now, we have to turn it into 2k + 1:

    n = 4x + 1

    We know that 4x = 2(2x), so if we set k = 2x, we get:

    n = 2k + 1

    Therefore, there is at least one x that causes n to be an odd integer for n = 4x + 1.

    Case 2:

    Again, we start with an assumption:

    n = 4x + 3

    We know that 4x + 3 = (4x + 2) + 1 and that 4x + 2 = 2(2x + 1), so that:

    n = 2(2x + 1) + 1

    If we set k = (2x + 1), we get:

    n = 2k + 1.


    The two x's we get specifically are x = \frac{1}{2}k, \ \frac{k-1}{2}

    The first x is for the form 4x + 1 and the second x is for the form 4x + 3.

    Therefore, there exists an integer x such that n is either 4x + 1 or 4x + 3.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prove theory
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 21st 2009, 12:08 PM
  2. [SOLVED] GCD Proof: Elem. Number Theory
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 9th 2009, 01:50 AM
  3. Elem Number Theory - gcd theorem in proof
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: October 2nd 2008, 11:16 AM
  4. elem. # theo - "prove never perfect square"
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: September 23rd 2008, 07:54 PM
  5. Replies: 2
    Last Post: September 14th 2008, 11:14 AM

Search Tags


/mathhelpforum @mathhelpforum