Question

Find the solution of linear diophantine equation with x+y minimum

Answer 1

Step-by-step explanation:

find one solution of the Diophantine equation with 2 unknowns, you can use the extended Euclidean algorithm. First, assume that a and b are non-negative. When we apply extended Euclidean algorithm for a and b, we can find their greatest common divisor g and 2 numbers xg and yg such that:

axg+byg=g

If c is divisible by g=gcd(a,b), then the given Diophantine equation has a solution, otherwise it does not have any solution. The proof is straight-forward: a linear combination of two numbers is divisible by their common divisor.

Now supposed that c is divisible by g, then we have:

a⋅xg⋅cg+b⋅yg⋅cg=c

Therefore one of the solutions of the Diophantine equation is:

x0=xg⋅cg,

y0=yg⋅cg.

The above idea still works when a or b or both of them are negative. We only need to change the sign of x0 and y0 when necessary.

Finally, we can implement this idea as follows (note that this code does not consider the case a=b=0)