Select Page

# Program for Extended Euclidean Algorithm using Python

by | Jul 21, 2021 | Python Programs

Home » Python » Python Programs » 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 ## 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

• A Full Stack Developer with 10+ years of experience in technical content creation.

• 