Calculate MCD and Bezout's identity

README.md

Calculate MCD and Bezout's identity

Run the script using Python

python mcd.py <first_number> <second_number>

Or just run the script and the numbers will be requested in interactive mode.

mcd.py

import sys

def mcd(first_number, second_number):
    if second_number > first_number:
        first_number, second_number = second_number, first_number

    mcd_steps = []

    print('MCD')
    while second_number > 0:
        mcd_steps.append((first_number, second_number, first_number//second_number, first_number%second_number))
        print(f'{first_number} = {second_number} * {first_number//second_number} + {first_number%second_number}')
        first_number, second_number = mcd_steps[-1][1], mcd_steps[-1][3]

    print('MCD =', mcd_steps[-1][1])
    print('\n-------------\n')

    print('Bezout')
    print(mcd_steps[-1][1], '=')
    start_row = mcd_steps[-2]
    # MCD = A * B + C * D
    a, b, c, d = 1, start_row[0], -start_row[2], start_row[3]
    for row in reversed(mcd_steps[:-2]):
        # X = B * Y + D
        x,y = row[0], row[2]
        a,b,c,d=c,x,a-c*y,b
        print(f'= {a} * {b} {c:+} * {d}')
        
print('N. 1 = ', end='')
if len(sys.argv) > 1:
    first_number = int(sys.argv[1])
    print(first_number)
else:
    first_number = int(input())

print('N. 2 = ', end='')
if len(sys.argv) > 2:
    second_number = int(sys.argv[2])
    print(second_number)
else:
    second_number = int(input())

print('\n-------------\n')

mcd(first_number, second_number)