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/