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.
Why This Mathematical Concept Matters
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.
- ●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.
📐 Examples — Click to Load
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.