Extended Euclidean Algorithm: Bézout Coefficients
The extended Euclidean algorithm finds gcd(a,b) and integers x,y such that ax+by=gcd(a,b). Used for modular inverse (RSA, CRT) and solving linear Diophantine equations.
Did our AI summary help? Let us know.
When gcd(a,b)=1, s is the modular inverse of a mod b. Used in RSA decryption and CRT solution construction. Linear Diophantine ax+by=c has solutions iff gcd(a,b) divides c.
Ready to run the numbers?
Why: Bézout identity: gcd(a,b) can always be written as ax+by. This finds the modular inverse of a mod b when gcd(a,b)=1—essential for RSA and Chinese Remainder Theorem.
How: Run Euclidean algorithm (a=bq+r) while tracking coefficients. Update s,t at each step: s_new = s_1 - q×s_2, t_new = t_1 - q×t_2. Final s,t are Bézout coefficients.
Run the calculator when you are ready.
Enter Integers
Step-by-Step Division Table
| Step | r₁ | r₂ | q | r | s | t |
|---|---|---|---|---|---|---|
| 1 | 56 | 42 | 1 | 14 | 1 | -1 |
| 2 | 42 | 14 | 3 | 0 | -3 | 4 |
GCD and Bézout Coefficients
Coprimality
📐 Step-by-Step Breakdown
For educational and informational purposes only. Verify with a qualified professional.
🧮 Fascinating Math Facts
Modular inverse: a⁻¹ mod m exists iff gcd(a,m)=1.
Bézout coefficients are not unique—add multiples of (b/gcd, -a/gcd).
📋 Key Takeaways
- • Extended Euclidean Algorithm finds gcd(a,b) and integers x, y such that ax + by = gcd(a,b)
- • Bézout's identity: such x, y always exist for any integers a, b
- • Used for modular inverse: if gcd(a,m)=1, then ax ≡ 1 (mod m) has solution x
- • Cryptography: RSA, linear Diophantine equations
💡 Did You Know?
📖 How It Works
Start with r₁=a, r₂=b, s₁=1, s₂=0, t₁=0, t₂=1. Repeatedly: q = ⌊r₁/r₂⌋, r = r₁ mod r₂, then update s = s₁ − q·s₂, t = t₁ − q·t₂, and shift. When r₂=0, gcd=r₁, x=s₁, y=t₁. The key is maintaining ax + by = gcd at each step.
📝 Worked Example: gcd(42, 56)
56 = 1×42 + 14
42 = 3×14 + 0
GCD = 14
Back-substitute: 14 = 56 − 1×42 → 42×(−1) + 56×1 = 14
Bézout: x = −1, y = 1
🚀 Real-World Applications
🔐 RSA
Private key: d = e⁻¹ mod φ(n) via EEA.
📐 Modular Inverse
Find a⁻¹ mod m when gcd(a,m)=1.
📜 Linear Diophantine
Solve ax + by = c when gcd(a,b)|c.
🌍 CRT
Chinese Remainder Theorem uses modular inverses.
🔢 Rational Approximations
Continued fractions, convergents.
💻 Coding Theory
Reed-Solomon, error correction.
⚠️ Common Mistakes to Avoid
- Sign errors: Bézout coefficients can be negative. Verify: a×x + b×y = gcd.
- Both zero: gcd(0,0) is undefined in this context.
- Confusing x and y: Order depends on whether a ≥ b or b > a.
- Not reducing: For modular inverse, reduce x mod m.
🎯 Expert Tips
💡 Modular Inverse
If gcd(a,m)=1, the x from ax+my=1 gives a⁻¹ mod m (reduce x mod m).
💡 Linear Diophantine
ax+by=c has solutions iff gcd(a,b) divides c.
💡 All Solutions
x = x₀ + k(b/d), y = y₀ − k(a/d) for integer k, d = gcd(a,b).
💡 Negative Inputs
Algorithm uses |a|, |b|; adjust signs of x,y as needed.
📊 Reference Table
| a, b | gcd | x, y |
|---|---|---|
| 42, 56 | 14 | 1, -1 |
| 240, 46 | 2 | -9, 47 |
| 17, 43 | 1 | 5, -2 |
📐 Quick Reference
🎓 Practice Problems
❓ FAQ
What is Bézout's identity?
For integers a, b with gcd d, there exist integers x, y such that ax + by = d.
How is this used for modular inverse?
If gcd(a,m)=1, extended GCD gives x with ax+my=1, so ax ≡ 1 (mod m).
Are x and y unique?
No. Infinitely many pairs exist. All have form x₀ + k(b/d), y₀ − k(a/d).
What if both numbers are zero?
gcd(0,0) is typically defined as 0, but the algorithm requires at least one non-zero.
Applications in cryptography?
RSA key generation uses extended GCD to find the private exponent.
Relationship to standard Euclidean?
Extended version tracks coefficients s, t through the same division steps.
Verify?
Check a×x + b×y = gcd. Plug in and compute.
📌 Summary
The Extended Euclidean Algorithm finds gcd(a,b) and Bézout coefficients x, y such that ax + by = gcd(a,b). It extends the standard Euclidean algorithm by tracking coefficients. Essential for modular inverses, RSA, and linear Diophantine equations.
✅ Verification Tip
Always verify: a×x + b×y should equal gcd(a,b). If it doesn't, check the signs and the algorithm steps.
🔗 Next Steps
Try the GCF Calculator for basic gcd, the Inverse Modulo Calculator for modular inverses, or the Chinese Remainder Theorem for congruence systems.
⚠️ Disclaimer: For educational use. Enter integers. Very large numbers may take longer.
Related Calculators
Inverse Modulo Calculator
Find the modular multiplicative inverse a^(-1) mod m using the Extended Euclidean Algorithm. Requires gcd(a,m)=1. Step-by-step solutions for cryptography...
MathematicsMultiplicative Inverse Modulo Calculator
Find the multiplicative inverse of a modulo m: a×x ≡ 1 (mod m). Uses the Extended Euclidean Algorithm with step-by-step trace. Applications in cryptography (RSA, Diffie-Hellman), linear congruences, and Chinese Remainder Theorem. Verify with Fermat's Little Theorem for prime moduli.
MathematicsChinese Remainder Theorem Calculator
Solve systems of congruence equations x ≡ a_i (mod m_i) using the Chinese Remainder Theorem. Step-by-step solution with multiple moduli, modular inverse, and...
MathematicsRelatively Prime Calculator
Check if two or more integers are relatively prime (coprime). GCD = 1 means no common factors. Euler totient, Euclidean algorithm, coprime pairs.
MathematicsPower Mod Calculator
Compute a^b mod m (modular exponentiation) using the fast square-and-multiply algorithm. Essential for cryptography (RSA, Diffie-Hellman), number theory, and...
MathematicsConsecutive Integers Calculator
Find n consecutive integers that sum to a target, or compute sum and product of consecutive integers. Supports even and odd consecutive sequences....
Mathematics