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
    10
    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
    10
    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, 07:48 AM
  2. diophantine equation
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 1st 2011, 08:19 AM
  3. Diophantine equation
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: January 16th 2011, 02:06 PM
  4. Diophantine Equation
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 8th 2010, 08:01 PM
  5. diophantine equation
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: June 3rd 2009, 06:08 AM

Search Tags


/mathhelpforum @mathhelpforum