Extended Euclidean Algorithm Calculator
Enter two integers to find their gcd and the numbers x and y.
A whole number.
A whole number.
Try
Result
You entered
Bézout coefficients
Least common multiple
Number of divisions
Show the work
Euclidean algorithm
Divide the larger number by the smaller, then the smaller by the remainder, and so on. The last non-zero remainder is .
Back-substitution
Each division says that a remainder is the number before the previous one minus a multiple of the previous one. Substituting upwards from the last step writes the gcd as a combination of the two starting numbers.
Bézout's identity
So there are whole numbers and with . Checking by multiplying out confirms it.
Using
Result
So , with and .