# Extended Euclidean Algorithm Calculator

> Find gcd(a, b) and integers x, y with ax + by = gcd, the modular inverse when it exists, and every step of the extended Euclidean algorithm.

Category: Algebra, geometry & advanced math · Applies to: Worldwide · Last updated: 2026-10-29
Interactive calculator: https://calculators.geekmidst.com/calculators/extended-euclidean-algorithm-calculator

The extended Euclidean algorithm finds the greatest common divisor and the Bézout coefficients x and y with ax + by = gcd(a, b). When the gcd is 1, x is the inverse of a modulo b.

Also called: Bézout identity calculator, Modular inverse calculator.

## Inputs
- a (default 240)
- b (modulus for the inverse) (default 46)

## Results
- gcd(a, b)
- x (coefficient of a)
- y (coefficient of b)
- Bézout identity
- Inverse of a modulo b
- lcm(a, b)
- Division steps

## Formula

```
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
```

Where:
- r: remainders
- q: quotients
- s, t: running coefficients with rᵢ = sᵢ·a + tᵢ·b

## Worked example
1. 240 = 5 × 46 + 10; 46 = 4 × 10 + 6; 10 = 1 × 6 + 4; 6 = 1 × 4 + 2; 4 = 2 × 2 + 0, so gcd = 2.
2. Back-substituting the quotients gives s = −9 and t = 47.
3. Check: 240 × (−9) + 46 × 47 = −2160 + 2162 = 2.

**Result:** 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).

## Related calculators
- [Greatest Common Factor Calculator](https://calculators.geekmidst.com/calculators/greatest-common-factor-calculator)
- [Chinese Remainder Theorem Calculator](https://calculators.geekmidst.com/calculators/chinese-remainder-theorem-calculator)
- [Modular Exponentiation Calculator](https://calculators.geekmidst.com/calculators/modular-exponentiation-calculator)

Source: GM¹X CalcVerse — https://calculators.geekmidst.com/calculators/extended-euclidean-algorithm-calculator