How to use this calculator
- Enter or choose a.
- Enter or choose b (modulus for the inverse).
- The gcd(a, b) updates as you type. Use Copy result or Share to keep it.
Method
r₀ = a, r₁ = b; qᵢ = ⌊rᵢ₋₁ ÷ rᵢ⌋, rᵢ₊₁ = rᵢ₋₁ − qᵢ·rᵢ, and likewise sᵢ₊₁ = sᵢ₋₁ − qᵢ·sᵢ, tᵢ₊₁ = tᵢ₋₁ − qᵢ·tᵢ (s: 1, 0; t: 0, 1) until r = 0
- r
- remainders
- q
- quotients
- s, t
- running coefficients with rᵢ = sᵢ·a + tᵢ·b
Worked example
- 240 = 5 × 46 + 10; 46 = 4 × 10 + 6; 10 = 1 × 6 + 4; 6 = 1 × 4 + 2; 4 = 2 × 2 + 0, so gcd = 2.
- Back-substituting the quotients gives s = −9 and t = 47.
- Check: 240 × (−9) + 46 × 47 = −2160 + 2162 = 2.
gcd(240, 46) = 2 = 240 × (−9) + 46 × 47. There is no inverse of 240 mod 46 because the gcd is not 1.
What the result means
If the gcd is 1, a and b are coprime and x mod b is the modular inverse of a, which is needed for RSA keys, solving linear congruences and the Chinese remainder theorem.
Assumptions and limits
- Exact big-integer arithmetic.
- x and y are the pair the standard algorithm produces; adding k·b/g to x and subtracting k·a/g from y gives the others.
- Inputs are capped at 200 digits each.
Questions
Are x and y unique?
No. If (x, y) works, so does (x + k·b/g, y − k·a/g) for any integer k. The algorithm returns the pair with the smallest magnitudes.
How do I get a positive inverse?
Take x mod b. For a = 3 and b = 11, x = 4, and 3 × 4 = 12 ≡ 1 (mod 11).