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 first number by the second, then the second by the remainder, and so on; because is smaller than , the first division has quotient and only swaps them. 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 .