# Arup Guha
# 8/26/2022
# Conversion of gcdhmk.c to Python

# Get input.
a = int(input("Enter a for your gcd calculation, a > 0\n"))
b = int(input("Enter b for your gcd calculation a > b > 0\n"))

# Store equations here.
eqns = []

# End when there's no remainder.
while b != 0:

    # Print out this line of the Euclidean Algorithm.
    print(a,"=",a//b,"x",b,"+",a%b)

    # Add this line to our transcript.
    nextLine = [a, a//b, b, a%b]
    eqns.append(nextLine)

    # Update for next iteration.
    savea = a
    a = b
    b = savea%b

# Index into equation list.
idx = len(eqns)-2
gcd = eqns[idx][3]

# Here is the first line that prints out.
backSub = [1, eqns[idx][0], -eqns[idx][1], eqns[idx][2]]

# Bubbling up the equations.
while idx >= 0:

    # This is the next equation to substitute into.
    print(backSub[0],"x",backSub[1],"+",backSub[2],"x",backSub[3],"=",gcd)

    # Get out!
    if idx == 0:
        break

    # This shows the actual substitution.
    print(backSub[0],"x",backSub[1],"+",backSub[2],"x (",eqns[idx-1][0],"+",-eqns[idx-1][1],"x",eqns[idx-1][2],") =",gcd)

    tmp = [backSub[2], eqns[idx-1][0], backSub[0]-backSub[2]*eqns[idx-1][1], backSub[1]]
    backSub = tmp;
    idx -= 1

# Print a solution
print("A solution (x,y) to ",backSub[1],"x + ",backSub[3],"y = ",gcd," is (", backSub[0],", ",backSub[2],").",sep="")

# Print Modular Inverse.
if gcd == 1:
    modinv = backSub[2]
    if modinv < 0:
        modinv += backSub[1]
    print(backSub[3],"inverse mod",backSub[1],"is",modinv)