Thread: Help finding an ax+by=c equation's integer solution

Hello All,

I have just begun a course on number theory and proofs, and I need help with the process of solving Diophantine equations. I am not sure how to employ the Euclidean algorithm to solve the following equation or how to go from that to the next step.

2011x + 1492y = 10,000

Could someone please explain the process to me? I need to determine whether this has integer solutions, but more importantly, I need to be able to understand and use this process on other such problems.

Thank you very much for your time.

Panglot

Originally Posted by panglot

Hello All,

I have just begun a course on number theory and proofs, and I need help with the process of solving Diophantine equations. I am not sure how to employ the Euclidean algorithm to solve the following equation or how to go from that to the next step.

2011x + 1492y = 10,000

Could someone please explain the process to me? I need to determine whether this has integer solutions, but more importantly, I need to be able to understand and use this process on other such problems.

Thank you very much for your time.

Panglot

Find gcg(1011,20)

If c/(gcg(1011,20)) is integer the you have a solution(Theorem)


Suppose that gcg(1011,20)=d, represent this d as linear combination(*) of 2011 and 20, now multiply d and (*) by k to get 1000, you will see one solution(x',y').

How you can find parametric form of all solutions?

Here is a look at a similar problem: 493x+ 215y= 100.

215 divides into 493 two times with remainder 63: 63= 493- 2(215).

63 divides into 215 three times with remainder 26: 26= 215- 3(63)

26 divides into 63 twice with remainder 11: 11= 63- 2(26)

11 divides into 26 twice with remainder 4: 4= 26- 2(11)

4 divides into 11 twice with remainder 3: 3= 11- 2(4)

3 divides into 4 once with remainder 1: 1= 4- 3

Now we can replace that 3 by 11- 2(4) from the previous equation: 1= 4-(11- 2(4)= 3(4)- 11.

We can replace that 4: 1= 3(26- 2(11))- 11= 3(26)- 7(11).

And replace that 11: 1= 3(26)- 7(63- 2(26))= 5(26)- 7(63).

And replace that 26: 1= 5(215- 3(63))- 7(63)= 5(215)- 22(63).

And replace that 63: 1= 5(215)- 22(493- 2(215))= 49(215)- 11(493).

Because we want 493x+ 215y= 100, not 1, multiply both sides of that previous equation by 100: (4900)(215)- (1100)(493)= 100.

That tells us that one solution is x= -1100, y= 4900.

But it is also easy to see that, for any integer k, x= -1100+ 215k, y= 4900- 493k is also a solution: 493(-1100+ 215k)+ 215(4900- 493k)= 493(-1100)+ (493)(215)k+ 215(4900)- (215)(493)k= 493(-1100)+ 215(4900) because the two "(215)(493)k" cancel.

HallsofIvy and Also Sprach Zarathustra, I have a question regarding extending this process:

Say, for example, I use Euclid's Algorithm to calculate that two possible integer solutions to the equation 20y + 13x = 1000 are y=2000 and x=-2000. How might I be able to establish two inequalities that would indicate whether any other integers are possible solutions to this?

Thank you both for your help--it is greatly appreciated.

Originally Posted by panglot

HallsofIvy and Also Sprach Zarathustra, I have a question regarding extending this process:

Say, for example, I use Euclid's Algorithm to calculate that two possible integer solutions to the equation 20y + 13x = 1000 are y=2000 and x=-2000. How might I be able to establish two inequalities that would indicate whether any other integers are possible solutions to this?

Thank you both for your help--it is greatly appreciated.

20*2000-13*1000 not equal to 1000.

I'm sorry, this should be 20*2000-13*3000=1000.

Originally Posted by panglot

I'm sorry, this should be 20*2000-13*3000=1000.

Here: Bézout's identity - Wikipedia, the free encyclopedia

Under Algorithm...

If and satisfy ax+ by= c, then , is also a solution for any integer k:

HallsofIvy,

Is there any way that one can set up some parameter of inequalities to establish whether or not x,y have solutions in the realm of natural numbers?