Extended Euclidean Algorithm

GCD with Bézout coefficients

a · x + b · y = gcd(a, b)
Greatest common divisor
6
Bézout coefficients
x (coefficient of a)
2
y (coefficient of b)
-3
Bézout identity
(48)·(2) + (30)·(-3) = 6
Coprime
No
Extended Euclidean AlgorithmStep-by-step Euclidean division reducing a and b to their greatest common divisor, then the Bézout identity a·x + b·y = gcd.Euclidean division steps48 = 1 × 30 + 1830 = 1 × 18 + 1218 = 1 × 12 + 612 = 2 × 6 + 0gcd = 6(48)·(2) + (30)·(-3) = 6