# Extended Euclid’s Algorithm C Code

Before going through this article, please look at my previous article about Euclid’s Algorithm. The Extended Euclid’s algorithm solves the following equation.
$GCD(a, b) = d = ax + by$
In addition to calculating a GCD, it calculates coefficients x and y such that satisfies the above equation. These coefficients x and y are important for calculating modular multiplicative inverses. The Extended Euclid’s algorithm is used in a much practical application specifically in cryptography.

The following C code presents an efficient algorithm to solve the Extended Euclid’s algorithm. The code is also available on GitHub.

SHARE Extended Euclid’s Algorithm C Code