Program for Extended Euclidean Algorithm using Python

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

Program for Extended Euclidean Algorithm using Python

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

 

 

Author

  • Barry Allen

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


Comments

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.