Extended Euclidean: find gcd(a,b) AND x,y with ax+by=gcd(a,b). Example: gcd(35,15)=5, with 35·1+15·(−2)=5. Bézout's identity guarantees such x,y always exist. The algorithm works by back-substitution through the GCD computation steps.
How to Use
Enter a and b:
- GCD: Greatest common divisor
- x,y: Bézout coefficients
- Steps: Full algorithm trace
The Algorithm
Run Euclidean: a=q₁b+r₁, b=q₂r₁+r₂, ... until remainder=0. Then back-substitute: express each remainder in terms of a,b. The last nonzero remainder is gcd(a,b) = ax+by.
Key Uses
- Modular inverse: a⁻¹ mod m (when gcd(a,m)=1)
- Solving linear Diophantine equations
- CRT construction
- RSA key generation
Step-by-Step Instructions
- 1Enter a and b.
- 2Run algorithm.
- 3Get gcd.
- 4Find x,y.
- 5Verify ax+by=gcd.