Solve the diophantine equation 71x +29y = 101
1.Euclidean algorithm
71 = 29*2 + 13
29 = 29*2 + 3
13 = 3*4 + 1
3 = 3*1 + 0
GCD(71,29) = 1
2. Write as linear equation (Euclidean algorithm backwards)
1 = 13 - 4*3
3 = 29 - 2*13
13 = 71 - 2*29
1 = 13 - 4*3 =
= 13 -4*(29 - 2*13)
= 9*13 -4*29
= 9*(71-2*29)-4*29
= 9*71 - 22*29
1 = 9*71 - 22*29 -> (write in the form 71x +29y = 101)
71(9) + 29(-22) = 1
71(909) + 29(-2222) = 101
71*909 + 29*(-2222) + 29*71n - 71*29n = 101
71(909-29n) + 29(-2222 + 71n) = 101
x = 909 - 29n
y = -2222 + 71n
Now that's my solution. But the correct solution should be:
x = -29n - 19
y = 71n + 50
Both solutions are correct. They are just different parametrizations of the same set of $(x,y)$. You have got $$x=909-29n,y=-2222+71n$$ for any integer $n$. You can plug any integer for $n$ and still got valid solution. Especially we can replace $n$ with $n+c$ for some constant $c$, shifting the parameter and still get valid solutions. Doing this we would get $$x=909-29c-29n,y=-2222+71c+71n.$$ Now you can see that choosing $c=32$ gives $$x=-19-29n, y=50+71n,$$ the expected solution. You might think of this as just inserting as many multiples of $29$ or $71$ as needed to make the parametrization simpler, but keep in mind that the parameter $n$ is same in both equations for $x$ and $y$, so you need to change both accordingly. Perhaps sometimes it might be also useful to view the solution in vector form instead:
$$(x,y)=(909,-2222)+n\cdot(-29,71).$$