Results 1 to 6 of 6
Like Tree3Thanks
  • 1 Post By emakarov
  • 1 Post By richard1234
  • 1 Post By OldDude

Math Help - Proof by contradiction

  1. #1
    Newbie
    Joined
    Dec 2012
    From
    England
    Posts
    8

    Proof by contradiction

    Use proof by contradiction to show that if a, b and c are odd integers then ax2 +bx+c = 0 has no solution in the set of rational numbers.
    (You may use standard parity results of the form "odd x odd = odd", "even + odd = odd", etc.)
    Don't understand how to prove this
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    Re: Proof by contradiction

    Assume that there is a rational solution x. How can x be written? Substitute this form of x into the equation and convert it into an equation that uses addition and multiplication only. Consider several cases when the variables occurring in the equation are even or odd. Only one of those cases is possible. But then the representation of x chosen in the beginning was not optimal in some sense.
    Thanks from dom139
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Jun 2012
    From
    AZ
    Posts
    616
    Thanks
    97

    Re: Proof by contradiction

    Suppose there is a rational root in the form x = \frac{p}{q} where p, q are relatively prime and q \neq 0. Then

    a(\frac{p}{q})^2 + b(\frac{p}{q}) + c = 0

    \frac{ap^2 + bpq + cq^2}{q^2} = 0 \Rightarrow ap^2 + bpq + cq^2 = 0

    Note that a,b,c are all odd. Can you find a parity contradiction here?
    Thanks from dom139
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Dec 2012
    From
    USA
    Posts
    2
    Thanks
    1

    Re: Proof by contradiction

    I am new to the forum and am an amateur, so I may have oversimplified.
    Move c to the right side of the equation, factor the left side by x, thus x has to divide c, which is odd, therefore x must be odd. Since a and b are odd, x(xa + b) is even, and we have a contradiction.
    Last edited by OldDude; December 21st 2012 at 12:24 PM. Reason: correcting error
    Thanks from emakarov
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    Re: Proof by contradiction

    Quote Originally Posted by OldDude View Post
    I am new to the forum and am an amateur, so I may have oversimplified.
    Move c to the right side of the equation, factor the left side by x, thus x has to divide c
    What does it mean for a rational number to divide an integer?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,150
    Thanks
    591

    Re: Proof by contradiction

    a,b,c odd => a = b = c = 1 (mod 2).

    thus, mod 2:

    ap2 + bpq + cq2 = 0 becomes:

    p2 + pq + q2 = 0 (mod 2)

    and since mod 2, p2 = p (a specific instance of fermat's "little theorem" for p = 2, but it's easy to verify directly 02 = 0, and 12 = 1, and (mod 2), 0 and 1 are "all there is"),

    p + pq + q = 0 (mod 2)

    if p = 0, q = 1 we have:

    0 + 0 + 1 = 0 (mod 2) can't happen.

    if p = 1, q = 0, we have:

    1 + 0 + 0 = 0 (mod 2) nope. never.

    if p = q = 1, we have:

    1 + 1 + 1 = 0
    0 + 1 = 0 sorry, wrong number.

    so the only legitimate possibility is p = q = 0 (mod 2):

    0 + 0 + 0 = 0 (mod 2). we have a winner!

    but wait! if p = q = 0 (mod 2), this means both p and q are EVEN.....so gcd(p,q) can't possibly be 1 (it has to be at LEAST 2).

    (arithmetic "mod 2" IS the "arithmetic of parity").
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. proof by contradiction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 2nd 2012, 07:12 AM
  2. Contradiction proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 4th 2010, 08:20 PM
  3. [SOLVED] direct proof and proof by contradiction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 27th 2010, 10:07 PM
  4. Proof by Contradiction: (n+2)^3 = n^3 + (n+1)^3 ?
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: October 3rd 2009, 06:04 AM
  5. proof by contradiction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: July 3rd 2009, 05:17 PM

Search Tags


/mathhelpforum @mathhelpforum