Table of Contents
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
0 Comments