I have a test coming up, and part of this test is using linear diophantine equations. Now I can obtain the gcd, but then I get stuck. I know it’s really simple… but I just cant’ get my head around it. Does anyone have a nice simple explanation and steps to follow?
It would be nice if you could use this example to explain, 1713x + 2000y = 3
cheers.
I know you know how to find the gcd, but let’s just start from the beginning:
1713x + 2000y = 3
Let’s find the gcd of 1713 and 2000:
2000 = 1713 * 1 + 287
1713 = 287 * 5 + 278
287 = 278 * 1 + 9
278 = 9 * 30 + 8
9 = 8 * 1 + 1
8 = 1 * 8 + 0
So 1 is the gcd. Write this as linear combination of 1713 and 2000; you can do this using the above equations in reverse order, step by step:
1 = 9 - 8
1 = 9 - (278 - 9*30) = -278 + 31 * 9
1 = -278 + 31 * (287 - 278) = 31 * 287 - 32 * 278
1= 31 * 287 - 32(1713 - 2875) = -321713 + 191*287
1 = -32 * 1713 + 191(2000 - 1713)
so 1 = 191 * 2000 - 223 * 1713
We want the linear combination to be equal to 3, not 1:
3 = 573 * 2000 - 669 * 1713
This is one of the solutions to the original equation. There are infinitely many more, and they are all of the form:
x = -669 + 2000n/gcd, y = 573 - 1713n/gcd, n an integer.
In this case, gcd = 1, of course, so our general solution is:
x = -669 + 2000n, y = 573 - 1713n