Extended Euclidean Algorithm
The extended Euclidean algorithm computes gcd(a,b) while also finding Bezout coefficients x,y satisfying ax+by=gcd(a,b).
Purpose
To compute modular inverses and solve linear Diophantine equations; a foundational tool in number theory and cryptography.
Mechanism
It maintains the coefficients while backtracking through the Euclidean algorithm: gcd(a,b)=gcd(b, a mod b), and on back-substitution x=y_prev, y=x_prev-floor(a/b)*y_prev. Time complexity O(log min(a,b)).
Use cases
- Modular inverse computation
- RSA key generation
- Linear Diophantine equations