Euclidean Algorithm Calculator

Find the GCD of two numbers using the Euclidean algorithm.

GCD 21

Number of steps 3

Formula: gcd(a, b) = gcd(b, a mod b)

Step-by-step with your numbers:

1. Values used:

2. First number = 252

3. Second number = 105

5. GCD = 21

6. Number of steps = 3

Did we solve your problem today?

The Euclidean algorithm efficiently finds the greatest common divisor by repeated remainders.

The math behind it

Replace (a, b) with (b, a mod b) repeatedly; when the remainder hits 0, the last non-zero value is the GCD.

gcd(252, 105) = 21.

Why is it so fast?

Each step roughly shrinks the numbers, so it finishes in very few iterations even for huge inputs.