Why does the Euclidean algorithm work?

Any number dividing both A and B also divides the remainder A % B, so gcd(A, B) = gcd(B, A % B). Replacing the pair with a smaller pair preserves the answer, and the remainders shrink until one reaches zero.

How do I compute the LCM from the GCD?

Use LCM(A, B) = A / GCD(A, B) * B. Dividing before multiplying keeps the intermediate value small and avoids the overflow that computing A * B first can cause.

How many steps does it take?

O(log(min(A, B))). The remainder at least halves every two steps, so even values near 10^18 finish in a few dozen iterations.

GCD & LCM

The GCD (greatest common divisor) and LCM (least common multiple) of two numbers are computed with the Euclidean algorithm.

SHRINK

mod

The chain so far

gcd(48, 18). Any number dividing both also divides their remainder — which is what lets the pair shrink without changing the answer.

48 mod 18 = 12. Replace the pair with (18, 12) — same divisors, smaller numbers.

Intuition

If a number divides both A and B, it must also divide their difference (A - B). By extension, it divides the remainder of A % B. We can keep reducing the problem until the remainder is 0.

Concept

GCD (Greatest Common Divisor): The largest number that divides both A and B without leaving a remainder.
LCM (Least Common Multiple): The smallest number that is a multiple of both A and B.
Relation: LCM(A, B) = (A * B) / GCD(A, B)

How it Works

Euclidean Algorithm:

Calculate remainder R = A % B.
If R == 0, then B is the GCD.
Otherwise, set A = B and B = R, and repeat.

Step-by-Step Breakdown

Watch the visualization:

See how the numbers shrink rapidly.
The process stops when the remainder becomes 0.
The last non-zero divisor is the GCD.

Trace: gcd(48, 18), then lcm(48, 18)

gcd(48, 18)

48 % 18 = 12. The remainder is not zero, so the pair becomes (18, 12) — any divisor of 48 and 18 also divides 12.

r = 12

gcd(18, 12)

18 % 12 = 6. Still not zero, so the pair becomes (12, 6).

r = 6

gcd(12, 6)

12 % 6 = 0. The remainder has vanished, so the divisor standing here is the answer.

r = 0

result

Three divisions. The last non-zero divisor is the GCD, and 6 does divide both 48 and 18.

gcd = 6

lcm(48, 18)

48 / 6 * 18. Dividing before multiplying keeps the intermediate value at 8 rather than the 864 that 48 * 18 would have produced first.

lcm = 144

When to Use

Simplifying fractions.
Scheduling problems (LCM).
Cryptography (RSA algorithm).

When NOT to Use

When numbers are extremely large (though it's still very efficient, O(log(min(A, B)))).

How to Identify

"Common divisor", "Simultaneous events (LCM)", "Simplify ratio".

Sample Problems

Greatest Common Divisor of Strings

Apply GCD concept to strings.

X of a Kind in a Deck of Cards

Find if groups have a common divisor size.

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description

Recursion Basics

Prime Numbers