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/