# Extended Euclid’s Algorithm C Code

$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.