Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: [Number Theory] Prove (x^2 - y^2) is not equal to 6.

  1. Aug 30, 2011 #1
    1. The problem statement, all variables and given/known data
    Prove the following proposition: For any positive integers x and y, (x^2 - y^2) is not equal to 6.


    2. Relevant equations


    3. The attempt at a solution

    I'll try to prove using contradition.
    Assume x^2 - y^2 = 6.
    (x+y)(x-y) = 6

    (x+y)=6 and (x-y)=1 (OR)
    (x+y)=1 and (x-y)=6 (OR)
    (x+y)=-6 and (x-y)=-1 (OR)
    (x+y)=-1 and (x-y)=-6 (OR)
    (x+y)=2 and (x-y)=3 (OR)
    (x+y)=3 and (x-y)=2 (OR)
    (x+y)=-2 and (x-y)=-3 (OR)
    (x+y)=-3 and (x-y)=-2

    When I solve those equations, x and y turns out to be fractions.
    Therefore, there is a contradition.
    Therefore, (x+y)(x-y) is not equal to 6.
    --------------------------------------
    Hi fellow physicsforumers
    This is my first post. :D
    I just started my discrete maths course at uni.
    Is my solution correct?
    Even if it is, is there any simpler way?
    Thanks,
    razefast
     
  2. jcsd
  3. Aug 30, 2011 #2

    lanedance

    User Avatar
    Homework Helper

    so its a proof of contradiction using cases - looks reasonable to me, though haven't done a heap of number theory

    i think though you need to state somewhere that the only 2 integer factorisations of 6 are
    1.6
    2.3
    -2.-3
    -1.-6

    interestingly, the brute force method is almost quicker here
    clearly x>y>0 for this to be true
    so say
    x=2, y=1, x^2-y^2=3
    x=3, y=2, x^2-y^2=5
    x=3, y=1, x^2-y^2=8
    x=4, y=3, x^2-y^2=7

    however you would also need to show x^2-(x-1)^2 is an monotonically increasing function, but that shouldn't be too hard
     
  4. Aug 30, 2011 #3
    Hi lanedance,

    Actually, I have no idea how to prove x^2-(x-1)^2 is an monotonically increasing function :(
    I have never learnt about monotonic function so I had to google it but still confused. lol
    Thanks for your reply lanedance :D

    With regards,
    razefast
     
  5. Aug 30, 2011 #4
    x^2 - (x-1)^2 is easy to prove as monotonic, even without calculus. I will give a different example so you get the idea.

    Monotonically Increasing Proof:
    f(x) = x^2+3x+1
    Prove that f(x) is monotonically increasing for x>0, that is,
    If 0<a<b, then f(a)<f(b)

    Let d=b-a => b=a+d.
    f(b)=f(a+d)=(a+d)^2 + 3(a+d) +1 = a^2 + 2ad + d^2 + 3a + 3d + 1 = f(a) + (2a + d + 3)d
    Now since 0<a<b, b-a>0 and so d>0. Thus (2a + d + 3)d > 0, and so f(b)>f(a).

    The problem of proving x^2 - (x-1)^2 is monotonic should be similar. In fact, it is a little algebraically simpler, and you should not need a restriction of x>0.
     
  6. Aug 30, 2011 #5

    lanedance

    User Avatar
    Homework Helper

    adding onto process91's comments

    monotonically increasing means it is always increasing as x gets bigger, or the derivative is always greater than zero

    in terms of the proof, we just want to show the gap between x^2 and (x-1)^2 is always greater than 6 for x>4. That way we don't have to check any values of x>4

    now expanding the difference
    x^2-(x-1)^2 = x^2-(x^2-2x+1) = 2x-1

    which is a straight line, hopefully you can convince yourself this is always increasing.

    Now say you have two integers s and t, if t>s can you show 2t+1>2s+1? That would be enough.

    All that said your original proof was fine with the extra line
    . This is just another way of looking at it.
     
  7. Aug 31, 2011 #6
    Hi lanedance and process91

    Those explanations are quite clear.
    I learnt new things today.
    Thx for helping out de newbie xD
    Man..Physics forums is great ^^
     
  8. Aug 31, 2011 #7

    verty

    User Avatar
    Homework Helper

    Here's another way, let x = y + k and try to derive a contradiction.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook