SimpleEuAlgDem

Euclidean Algorithm

Find the Greatest Common Divisor (GCD) step by step

Enter number $a$:

Enter number $b$:

How the Euclidean Algorithm Works

The Euclidean algorithm finds the Greatest Common Divisor (GCD) of two integers by repeatedly applying the division algorithm:

1. Given non-negative two numbers $a$ and $b$, ensure $a \ge b$
2. If $b = 0$, then $\gcd(a, b) = a$
3. Otherwise, replace $a$ with $b$ and $b$ with $a \mod b$
4. Repeat until $b = 0$