Thread: 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.

Originally Posted by Ideasman

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

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?

Originally Posted by Ideasman

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".

Originally Posted by ThePerfectHacker

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

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.

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?

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