Extended Euclidean Algorithm (EEA)

The EEA computes the GCD of two integers and their Bézout coefficients, playing a fundamental role in number theory and cryptography.

The extended Euclidean algorithm computes the GCD of two integer numbers while determining the Bézout coefficients 𝑥 and 𝑦 such that 𝑎𝑥+𝑏𝑦=gcd(𝑎,𝑏). This method is particularly useful in number theory and cryptography, especially for computing modular inverses, which are essential in methods such as RSA encryption.

The attached livescript provides the implementation of the extended Euclidean algorithm in both recursive and iterative versions. Each version is accompanied by an explanation of its correctness.