Enter two positive integers a and b. This tool shows each step of the Euclidean algorithm and then computes integers x and y such that gcd(a,b) = xa + yb.
At each step, we divide the larger current number by the smaller one:
The last nonzero remainder is the gcd. To find Bézout coefficients, we also track each remainder as a linear combination of the original inputs.