Extended Euclidean Algorithm Calculator

About this calculator

The Extended Euclidean Algorithm builds on Euclid's classical method for finding the greatest common divisor (GCD) of two integers, but goes a step further: alongside the GCD it also produces integer coefficients x and y, known as Bézout's coefficients, such that ax + by = gcd(a, b), an identity guaranteed to exist for any two integers by Bézout's identity.

These coefficients aren't just a mathematical curiosity: computing the modular inverse of a number (needed constantly in cryptography, including the key generation and decryption steps of RSA) relies directly on the extended Euclidean algorithm, and it's also the standard tool for solving linear Diophantine equations, equations in integers of the form ax + by = c, and for simplifying fractions and solving problems in modular arithmetic more generally.

Enter two positive integers and this calculator runs the extended Euclidean algorithm to return their GCD along with the Bézout coefficients x and y.