Euclidean Algorithm Calculator

Find the GCD of two numbers with full step-by-step Euclidean algorithm trace.

About Euclidean Algorithm Calculator

The Euclidean algorithm finds the greatest common divisor (GCD) of two integers by repeated division. At each step, replace the larger number with the remainder of dividing the larger by the smaller: gcd(a, b) = gcd(b, a mod b). When the remainder is 0, the last non-zero remainder is the GCD. The algorithm terminates in at most O(log(min(a,b))) steps.

Formula

Euclidean algorithm

gcd(a, b) = gcd(b, a mod b), with gcd(a, 0) = a

a: First integer
b: Second integer

Worked example

With the default values below, Euclidean Algorithm Calculator returns GCD of 21. Change any input above and every figure here is recalculated in your browser.

Inputs used

First Number (a)minimum 0: 252
Second Number (b)minimum 0: 105

Results

GCD: 21
Steps Required: 3

Step by step

1Step 1
2Step 2
3Step 3
4GCD= 21

Assumptions and limits

The result is derived only from the 2 inputs listed above. Anything not among them is not part of the calculation.
In particular, this calculator does not take inflation, tax, fees or charges or compounding frequency into account.
Figures are rounded for display to whole numbers, so totals built from several rounded parts can differ slightly from the unrounded arithmetic.

How these calculators are built and tested is described on the Methodology page. If a figure looks wrong, please report it.

Frequently Asked Questions

How is this different from the GCF calculator?

The GCF calculator computes the result directly. This calculator shows every step of the Euclidean algorithm — each division, quotient and remainder — making it a learning tool for understanding the process.

How fast is the Euclidean algorithm?

It takes at most O(log(min(a,b))) steps. The worst case is consecutive Fibonacci numbers, where each step reduces the pair by approximately the golden ratio.