euclidean.py

import sys


def e(a, b, px, py, d=0):
    print("    " * d, f"e({a}, {b}, {px[1]}, {py[1]})")
    if b == 0:
        px[0] = 1
        py[0] = 0
        print("    " * d, f"{px[1]} <- 1, {py[1]} <- 0")
        return
    e(b, a % b, py, px, d + 1)
    print(
        "    " * d,
        f"{py[1]} = {py[1]}({py[0]}) - {a} // {b} * {px[1]}({px[0]}) =",
        end="",
    )
    py[0] -= a // b * px[0]
    print(f" {py[0]}")


def main(a, b):
    x = [-999999, "x"]
    y = [-999999, "y"]
    e(a, b, x, y)
    print(f" {x[0]}, {y[0]}")


main(int(sys.argv[1]), int(sys.argv[2]))

# $ ./e.py 111 30
#  e(111, 30, x, y)
#      e(30, 21, y, x)
#          e(21, 9, x, y)
#              e(9, 3, y, x)
#                  e(3, 0, x, y)
#                  x <- 1, y <- 0
#              x = x(1) - 9 // 3 * y(0) = 1
#          y = y(0) - 21 // 9 * x(1) = -2
#      x = x(1) - 30 // 21 * y(-2) = 3
#  y = y(-2) - 111 // 30 * x(3) = -11
#  3, -11

# $ ./e.py 30 111
#  e(30, 111, x, y)
#      e(111, 30, y, x)
#          e(30, 21, x, y)
#              e(21, 9, y, x)
#                  e(9, 3, x, y)
#                      e(3, 0, y, x)
#                      y <- 1, x <- 0
#                  y = y(1) - 9 // 3 * x(0) = 1
#              x = x(0) - 21 // 9 * y(1) = -2
#          y = y(1) - 30 // 21 * x(-2) = 3
#      x = x(-2) - 111 // 30 * y(3) = -11
#  y = y(3) - 30 // 111 * x(-11) = 3
#  -11, 3

# $ ./e.py 7 11
#  e(7, 11, x, y)
#      e(11, 7, y, x)
#          e(7, 4, x, y)
#              e(4, 3, y, x)
#                  e(3, 1, x, y)
#                      e(1, 0, y, x)
#                      y <- 1, x <- 0
#                  y = y(1) - 3 // 1 * x(0) = 1
#              x = x(0) - 4 // 3 * y(1) = -1
#          y = y(1) - 7 // 4 * x(-1) = 2
#      x = x(-1) - 11 // 7 * y(2) = -3
#  y = y(2) - 7 // 11 * x(-3) = 2
#  -3, 2

# $ ./e.py 7 5
#  e(7, 5, x, y)
#      e(5, 2, y, x)
#          e(2, 1, x, y)
#              e(1, 0, y, x)
#              y <- 1, x <- 0
#          y = y(1) - 2 // 1 * x(0) = 1
#      x = x(0) - 5 // 2 * y(1) = -2
#  y = y(1) - 7 // 5 * x(-2) = 3
#  -2, 3