Extended Euclidean Algorithm

algorithm
mathematical-algorithm
euclidean-algorithm
greatest-common-divisor
extended-euclidean-algorithm
(Team) #1

In this article, we will demonstrate Extended Euclidean Algorithm. For this, we will see how you can calculate the greatest common divisor in a naive way which takes O(N) time complexity which we can improve to O(log N) time complexity using Euclid's algorithm. Following it, we will explore the Extended Euclidean Algorithm which has O(log N) time complexity.

Read this article to understand Extended Euclidean Algorithm in depth

Have a doubt or thought? Join the discussion now


This is a companion discussion topic for the original entry at http://iq.opengenus.org/extended-euclidean-algorithm/