GCD and Extended GCD

#두 수를 나누어 가면서 그 나머지가 0이 될 때까지 반복
def gcd(a, b):
    print("gcd value({}, {}) : ".format(a, b), end = '')
    if a < b: # 큰 수가 앞에 오도록 값 교환
        a, b = b, a
    while b != 0: # 나머지가 0이 될 때
        a, b = b, a% b
    print(a) #최대공약수 출력

#두 수를 division을 통해 구함
def extended_gcd(a, b):
    #초기 설정을 위한 초기화
    r1, r2 = a, b
    s1, s2 = 1, 0
    t1, t2 = 0, 1
    
    while(r2 > 0):
        q = r1 // r2
        r = r1 - q * r2 #q는 r2로 r1을 나눈 몫, r은 그 나머지
        r1, r2 = r2, r #r1은 r2로, r2는 r로 초기화
 
        s = s1 - q * s2 #q는 s2로 s1을 나눈 몫, s는 그 나머지
        s1, s2 = s2, s #s1은 s2로 s2는 s로 초기화
 
        t = t1 - q * t2 #q는 t2로 t1을 나눈 몫, t은 그 나머지
        t1, t2 = t2, t #t1은 t2로 t2는 t로 초기화
 
    print("{} = ({})*{} + ({})*{}".format(r1, s1, a, t1, b))
    #출력형식은 다음과 같다. r1 = (s1)*a + (t1)*b

#gcd(45, 75)
#extended_gcd(45, 75)
#gcd(666, 1414)
#extended_gcd(666, 1414)
#gcd(102, 222)
#extended_gcd(102, 222)

extended_gcd(10, 21)