Introduction

The task is to find GCD of two numbers using extended Euclidean algorithm.

Program

def find(num1, num2): 


    if num1 == 0 :  
        return num2, 0, 1
            
    output, n, m = find(num2 % num1, num1) 
    
    n1 = m - ( num2//num1 ) * n 
    m1 = n 
    
    return output,n1,m1


num1 = int(input("Enter the first number: "))
num2 = int(input("Enter the second number: "))
output, n1, m1 = find(num1, num2) 
print("The gcd({0},{1}) is {2} ".format(num1, num2 ,output))

Output

Explanation

Extended Euclidean Algorithm : an + bm = GCD(a,b), where n and m are integer coefficients.

The function find() is recursively called to update the GCD value where as m1 and n1 are updated by expression:

n1 = m - ( num2//num1 ) * n 
m1 = n