Extended Euclidean Calculator
Extended Euclidean algorithm (Bezout)
Client-side computation for analysis, verification, and learning. Do not paste production secrets into untrusted sites; prefer local tooling for key material.
Educational / engineering use. RSA mode uses tiny primes for illustration only—not for real key generation.
a
b
Add Extended Euclidean Calculator Free On Your Website
Paste this HTML on your site.
What is Extended Euclidean Calculator?
An extension of the Euclidean algorithm that, along with the GCD, also computes the Bezout coefficients integers satisfying ax + by = gcd(a, b). Fundamental in modular inverse calculation and number theory.
Extended Euclidean Formula
Bézout coefficients at each step:
Until b = 0, then gcd = a, x = 1, y = 0.
Step-by-Step
- Enter integers a and b.
- Run Euclidean divisions.
- Back-substitute to express gcd as ax + by.
- Return gcd, x, and y.
- Use x for modular inverse when applicable.
Worked Example
Where Extended Euclidean Calculator Is Applied
- Computing modular inverses for RSA key generation
- Polynomial GCD in algebra systems
- Solving Diophantine equations in mathematics
- Lattice-based cryptography
- Compiler design (register allocation problems)
- Chinese Remainder Theorem computations
Related Cryptography Calculators
Explore similar calculators to streamline your workflow.