Extended Euclidean Algorithm Calculator

How to Use This Calculator

1. Enter integers a and b. The gcd and Bézout coefficients appear instantly.
2. Use Find Mod Inverse tab when you need a⁻¹ mod m.
3. Use Linear Diophantine tab to solve ax + by = c.
4. Use Professional for step-by-step division tableau and complexity analysis.

Formula

Example

Frequently Asked Questions

• What is the Extended Euclidean Algorithm? ▼
  It extends the basic Euclidean algorithm to find integers x and y satisfying a·x + b·y = gcd(a,b) (Bézout's identity). These coefficients are used to compute modular inverses.
• How are Bézout coefficients used? ▼
  If gcd(a,m)=1, then a·x + m·y = 1 means a·x ≡ 1 (mod m), so x is the modular inverse of a. This is the foundation of RSA key generation.
• When does ax + by = c have integer solutions? ▼
  The linear Diophantine equation ax+by=c is solvable in integers if and only if gcd(a,b) divides c. The Extended Euclidean algorithm finds the particular solution.
• What is the complexity of the algorithm? ▼
  O(log min(a,b)) division steps — exponentially faster than trial methods. For 1000-digit numbers it needs only ~3000 steps.
• Who invented this algorithm? ▼
  The basic form appears in Euclid's Elements (≈300 BC). The extended form giving Bézout coefficients was studied by Bachet de Méziriac in 1624 and formalized by Euler and Gauss.

Related Calculators