Results 1 to 8 of 8

Math Help - Diophantine Equation

  1. #1
    Member
    Joined
    Sep 2006
    Posts
    221

    Diophantine Equation

    Solve: 100y + x - 68 = 2*(100x + y)

    I know the answer is x = 10; y = 21, but I did that from trial and error. Can you show me step by step how to solve this. I believe you use Euclidean Algorithm to find a gcd, and then you use the reverse Euclidean Algorithm to find a and b, such that:

    d = gcd(a, b)

    And then you have to use these equations:

    x = x_0 + (b/d)*n AND y = y_0 - (a/d)*n

    This should give a general solution, I believe.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Ideasman View Post
    Solve: 100y + x - 68 = 2*(100x + y)
    My favorite way is through continued fractions.
    But since this seems like the beginning of number theory course I will not mention it.

    100y+x-68=2(100x+y)
    100y+x-68=200x+2y
    98y-200x=68
    Let x'=-x,
    200x'+98y=68
    Divide,
    100x'+49y=34
    This is a linear diophantine equation.
    gcd(100,49)=1, solutions therefore exist in Z.

    Using Euclidean Algorithm we find that:
    100=2(49)+2
    49= 24(2)+1
    2=2(1)+0
    Thus, the gcd(49,100)=1 as expected.

    Working backwards we find that,
    49-24(2)=1
    49-24(100-2*49)=1
    49-24*100+48*49=1
    49(49)+100(-24)=1
    100(-24)+49(49)=1
    Multiply by 34,
    100(-816)+49(1666)=34
    Thus,
    x'=-816+49t
    y=1666-100t
    Thus,
    x=816-49t
    y=1666-100t
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Sep 2006
    Posts
    221
    Thanks, TPH. How do they get the answer of (10, 21)? I tried letting your t = 0 and then plugging in the x and y to see if it is equal, but they weren't equal?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Ideasman View Post
    Thanks, TPH. How do they get the answer of (10, 21)? I tried letting your t = 0 and then plugging in the x and y to see if it is equal, but they weren't equal?
    Since you want positive solutions.


    You need to solve,
    x'>0
    y>0

    This pair of inequalities for "t".
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Sep 2006
    Posts
    221
    Quote Originally Posted by ThePerfectHacker View Post
    Since you want positive solutions.


    You need to solve,
    x'>0
    y>0

    This pair of inequalities for "t".
    When do these following equations get used:

    x = x_0 + (b/d)*n AND y = y_0 - (a/d)*n
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Sep 2006
    Posts
    221
    Okay, I believe you use the equations to find the pos. x/y..since you need to incorporate n in there somehow.

    100y+x-68=2(100x+y)
    100y+x-68=200x+2y
    98y-200x=68

    Regarding your above steps there, why is it -200x? Shouldn't it be -199x?

    This, then, would affect the whole answer and maybe that's why I was running into difficulty.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Sep 2006
    Posts
    221
    I tried manipulating the results to fix your error, but I still can't get x = 10, y = 21 for an answer :-\. You were, however, right that they are both meant to be positive. Any idea?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Sep 2006
    Posts
    221
    Due in 3 hours, if anyone knows how to do it. I know the answer is x = 10, y = 21....but I can't get the diophantine to work! Grr
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. yet another Diophantine equation
    Posted in the Number Theory Forum
    Replies: 12
    Last Post: September 7th 2011, 06:48 AM
  2. diophantine equation
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 1st 2011, 07:19 AM
  3. Diophantine equation
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: January 16th 2011, 01:06 PM
  4. Diophantine Equation
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 8th 2010, 07:01 PM
  5. diophantine equation
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: June 3rd 2009, 05:08 AM

Search Tags


/mathhelpforum @mathhelpforum