Program for Extended Euclidean Algorithm using Python


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


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))


Program for Extended Euclidean Algorithm using Python


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




  • Barry Allen

    A Full Stack Developer with 10+ years of experience in different domain including SAP, Blockchain, AI and Web Development.


Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.