Euclidean Algorithm(EA) and Extended Euclidean Algorithm(EEA)

getGCD.py

def getGCD(num_1, num_2):
    if num_2 > num_1:
        tmp = num_1
        num_1 = num_2
        num_2 = tmp
    while True:
        remainder = num_1 % num_2
        if remainder == 0:
            return num_2
        num_1 = num_2
        num_2 = remainder
        
def EEA(r0, r1):
    # Extended Euclidean algorithm
    S = [1, 0]
    T = [0, 1]
    R = [r0, r1]
    i = 1
    while True:
        i += 1
        R.append(R[i - 2] % R[i - 1])
        q = (R[i-2]-R[i])/R[i-1]
        S.append(S[i-2]-q*S[i-1])
        T.append(T[i-2]-q*T[i-1])
        if R[i - 2] % R[i - 1] == 0:
            break
    print("gcd(", r0, ", ", r1, ") = (",
          int(S[i-1]), ") * ", r0, " + (", int(T[i-1]), ") * ", r1)
    return S[i-1], T[i-1]


print(getGCD(2, 3))
print(getGCD(27, 21))
print(getGCD(973, 301))
a, b = EEA(973, 301)