What is the Euclidean algorithm?

It is an efficient method for finding the GCD of two integers by repeatedly replacing the larger number with the remainder of dividing the larger by the smaller, until the remainder is 0. The last non-zero remainder is the GCD.

How many steps does the algorithm take?

At most O(log min(a, b)) steps. In practice it is very fast — even for numbers with hundreds of digits it finishes in dozens of iterations.

What are Bezout coefficients?

Integers x and y such that a·x + b·y = GCD(a, b). The extended Euclidean algorithm finds them by back-substituting through the division steps. They are used in modular inverses and solving linear Diophantine equations.

Does the tool handle negative numbers?

Yes. The GCD is defined as positive, so the tool operates on absolute values internally. Bezout coefficients may be negative.

What happens if one input is 0?

GCD(a, 0) = a by convention. The algorithm stops immediately at step 1 with no divisions needed.

Euclidean Algorithm Steps

Enter two integers and see every step of the Euclidean algorithm — division, remainder, and the final GCD.

Enter Two Integers

First number (a)

Second number (b)

Show extended algorithm (Bezout coefficients)

Quick examples

Division Steps

Step	Equation	Dividend	Divisor	Quotient	Remainder

Back-substitution (Extended Algorithm)

Expresses GCD as a linear combination: a·x + b·y = GCD

Step	x coefficient	y coefficient	Value

Enter two integers above and click Compute.

Summary

Enter two integers and see every step of the Euclidean algorithm — division, remainder, and the final GCD.

How it works

Enter two integers (positive or negative) in the input fields.
The tool applies the Euclidean algorithm: repeatedly replace (a, b) with (b, a mod b) until b = 0.
Each iteration is shown as a row: a = q × b + r.
The last non-zero remainder is the GCD.
Enable "Extended algorithm" to back-substitute and find Bezout coefficients x, y such that ax + by = GCD.

Use cases

Check Euclidean algorithm homework step by step.
Verify the GCD before simplifying a fraction.
Learn how the algorithm reduces large numbers to small ones quickly.
Use Bezout coefficients to solve linear Diophantine equations.
Confirm coprimeness: GCD = 1 means the numbers share no factors.
Understand why the algorithm terminates in O(log min(a,b)) steps.

Frequently Asked Questions

Last updated: 2026-09-22 · Reviewed by Nham Vu