LINEAR DIOPHANTINE EQUATIONS
The Python function isolve(a,b,c) produces an integer
solution of the equation
ax + by = c,
where a, b, and c are integers. It is assumed that
the equation is solvable, i.e., that c divides
the gcd of a and b. Otherwise its output is not
correct. The solution is found recursivley using t
the Euclidean algorithm.
EXAMPLE:
>>> isolve(1234,4321,1)
[-1082, 309]
Note that divmod(a,b) returns a tuple consisting
of the quotient and remainder computed when a is
divided by b. Thus divmod(17,3) = (5,2)
----------------------------------------------------
def isolve(a,b,c):
"""isolve(a,b,c): return solution of ax + by = c.
Recursive implementation."""
qr = divmod(a,b)
q = qr[0]
r = qr[1]
if r == 0:
return( [0,c/b] )
else:
sol = isolve( b, r, c )
u = sol[0]
v = sol[1]
return( [ v, u - q*v ] )