from sys import argv

def gcdEuclid(a, b):
        if b == 0:
            return "gcd(" + str(a) + ", 0) = " + str(a) + "\n";
        else:
            result = "gcd(" + str(a) + ", " + str(b) + ") = gcd(" + str(b) + ", " + str(a) + " mod " + str(b) + ")\n"
            return result + gcdEuclid(b, a % b)

def gcdDivision(a, b):
        if b == 0:
            return ""
        else:
            result = str(a) + " = " + str(a // b) + " * " + str(b) + " + " + str(a % b) + "\n"
            return result + gcdDivision(b, a % b)

def gcdLinear(a, b):
        if b % (a % b) == 0:
            quotient = a // b
            text = str(a % b) + " = 1 * " + str(a) + " - " + str(quotient) + " * " + str(b) + "\n"
            return (1, -quotient, text)
        else:
            x, y, text = gcdLinear(b, a % b)
            coeffToKeep = y;
            modifiedCoeff = x - y * (a // b);
            text += "= " + str(coeffToKeep) + " * " + str(a) + " " + ("- " if modifiedCoeff < 0 else "+ ") + str(abs(modifiedCoeff)) + " * " + str(b) + "\n"
            return (coeffToKeep, modifiedCoeff, text)

def gcd(a, b):
        if b == 0:
            return a;
        else:
            return gcd(b, a % b)

a = int(argv[1])
b = int(argv[2])
print();
print(gcdEuclid(a, b))
if a < b:
    a, b = b, a
print(gcdDivision(a, b))
if a % b != 0 and b % a != 0:
    x, y, text = gcdLinear(a, b)
    print(text)
    if gcd(a, b) == 1:
        print(str(x) + " er inversen til " + str(a) + " modulo " + str(b))
        print(str(y) + " er inversen til " + str(b) + " modulo " + str(a))