How this calculator works
Each table row divides the previous divisor into the previous dividend. Replacing a pair by its divisor and remainder preserves their common divisors. The last non-zero remainder is therefore the greatest common divisor. Tracking how each remainder combines the original integers gives the extended coefficients x and y. Divisions use absolute values; the final identity restores the original signs. Internal integer arithmetic keeps the coefficients exact.
Formula
a = qb + r, with 0 ≤ r < |b|; gcd(a,b) = gcd(b,r). The extended algorithm finds integers x,y with ax + by = gcd(a,b).
Worked example
For 240 and 46, the divisions have remainders 10, 6, 4, 2 and 0. The GCD is 2. The coefficients -9 and 47 verify the result: 240 × (-9) + 46 × 47 = -2160 + 2162 = 2.
Advertisement
Frequently asked questions
Why does the table sometimes start with quotient zero?
If the first absolute value is smaller than the second, the first division has quotient zero and swaps their roles. It remains a valid Euclidean step.
Are the Bézout coefficients unique?
No. For GCD g, replacing x by x + t(b/g) and y by y - t(a/g) gives another pair for any integer t.
What happens when one value is zero?
The GCD is the magnitude of the other integer. Two zeros are rejected because there is no greatest positive common divisor.