euclid-extended

#!/usr/bin/env python

def euclidExtended(a, b):
    if b == 0:
        return a, 1, 0
    dd, xx, yy = euclidExtended(b, a % b)
    d, x, y = dd, yy, xx - int(a / b) * yy
    print a, b, d, x, y
    return d, x, y

def solveLinearModularEquation(a, b, n):
    d, xx, yy = euclidExtended(a, n)
    #print d, xx, yy
    if (b % d == 0):
        x0 = (xx * (b / d)) % n
        print x0
        for i in xrange(0, d):
            print (x0 + i * (n / d)) % n,
    else:
        print "No solution."

#ax=b(mod c)
solveLinearModularEquation(a, b, c)