What is the extended Euclidean algorithm?

It is an extension of the standard Euclidean algorithm that, in addition to finding gcd(a, b), also computes integers s and t satisfying Bezout's identity: a·s + b·t = gcd(a, b).

What are Bezout coefficients?

Bezout coefficients are the integers s and t such that a·s + b·t = gcd(a, b). They are not unique — infinitely many pairs satisfy the equation, but the algorithm returns the pair with smallest absolute values.

How is this used to find a modular inverse?

If gcd(a, m) = 1, then the coefficient s from a·s + m·t = 1 is the modular inverse of a mod m. Reduce s modulo m to get a positive result.

Does the order of a and b matter?

The GCD is the same regardless of order, but the Bezout coefficients s and t are swapped. If you enter (a, b) and get (s, t), then entering (b, a) yields coefficients (t, s).

What happens if one input is zero?

gcd(a, 0) = a and gcd(0, b) = b by convention. The algorithm handles this correctly, returning the non-zero value as the GCD with coefficients (1, 0) or (0, 1).

Can I use negative integers?

Yes. The GCD is always returned as a non-negative value. Bezout coefficients may be negative, which is expected and mathematically correct.

Extended Euclidean Calculator

Name: Extended Euclidean Calculator
Availability: InStock
Author: Nham Vu

Enter two integers to find their GCD and Bezout coefficients (s, t) with a step-by-step extended Euclidean algorithm table.

Inputs

Integer a

Integer b

Step-by-Step Table

Enter values and click Calculate to see the steps.

Step	Dividend	Divisor	Quotient	Remainder	s	t

Each row: dividend = quotient × divisor + remainder. Columns s and t track the Bezout coefficients via back-substitution.

How to read the table

Each row performs one division step: dividend = quotient × divisor + remainder.
The s and t columns are updated as: s_new = s_prev − quotient × s_curr (same for t).
The last non-zero remainder is the GCD. The s and t values in that row are the Bezout coefficients.
Highlighted row is the final step where the remainder reaches zero.

Summary

Enter two integers to find their GCD and Bezout coefficients (s, t) with a step-by-step extended Euclidean algorithm table.

How it works

Enter two integers a and b in the input fields.
Click Calculate to run the extended Euclidean algorithm.
The step-by-step table shows each division, quotient, and coefficient update.
Read the GCD and Bezout coefficients s, t from the final result row.
Verify: a·s + b·t should equal the GCD shown.

Use cases

Find the modular inverse of a number (when gcd = 1, s is the inverse of a mod b).
Solve linear Diophantine equations of the form a·x + b·y = c.
Check whether two integers are coprime (GCD = 1).
Cryptography coursework — RSA key generation requires extended GCD.
Number theory homework — verify Bezout identity by hand.
Competitive programming — precompute modular inverses quickly.

Frequently Asked Questions

Last updated: 2026-06-13 · Reviewed by Nham Vu