How this calculation works
Adding b/g to x and subtracting a/g from y produces another valid pair, where g is the gcd.
ax + by = gcd(a,b)A worked example
30 × (−1) + 18 × 2 = 6.
Good to know
Several coefficient pairs can give the same gcd.
Reference: NIST DLMF, Functions of Number Theory (opens in a new tab) ↗
Work backward through the Euclidean divisions
For 30 and 18, Euclidean division gives 30 = 18 + 12 and 18 = 12 + 6. The last nonzero remainder is 6. Substitute 12 = 30 − 18 into 6 = 18 − 12 to obtain 6 = 18 − (30 − 18) = −30 + 2 × 18.
The coefficients are therefore x = −1 and y = 2 in 30x + 18y = 6. Multiplying and adding the two terms gives −30 + 36 = 6, which checks the result. The extended Euclidean algorithm tracks the same substitutions while computing the gcd.
Understand why the coefficient pair is not unique
If ax + by = d with d = gcd(a,b), adding b/d to x and subtracting a/d from y preserves the sum. For this example, adding 3 to −1 and subtracting 5 from 2 gives x = 2 and y = −3. The check becomes 60 − 54 = 6.
The calculator reports one valid pair rather than listing every pair. For a target c, the equation ax + by = c has an integer solution exactly when d divides c. Multiplying the default coefficients by two therefore gives a solution for target 12. When the gcd is one, the Modular inverse calculator uses one of these coefficients as an inverse modulo the other input.
A few questions, answered
Do the coefficients have to be positive?
No. Negative coefficients are often necessary to make a small gcd from larger positive inputs.
What if I swap the inputs?
A valid identity can be obtained by swapping the coefficient roles as well. The particular pair returned by the algorithm can differ.