linear diofantic equation solver python code example

Example: diophantine equation python

def EuclideanGcd(a, b):
	if b:
		return EuclideanGcd(b, a%b)
	else:
		return a

def extendEuclidean(a, b, s1=1, s2=0, t1=0, t2=1):    
    if b:
        r=a%b
        return extendEuclidean(b, r, s2, s1-s2*(a//b), t2, t1-t2*(a//b))
    
    return a, s1, t1

def diophantine(a, b, c):
    d=EuclideanGcd(a, b)
    if c%d:
        return None
    _, x1, y1 = extendEuclidean(a//d, b//d)

    return x1*c//d, f'{x1*c//d} + k{b//d}', y1*c//d, f'{y1*c//d} - k{a//d}'