Problem Statement

GCD and LCM

You are given two whole numbers, a and b. You need to find two things about them. The first is the GCD, short for Greatest Common Divisor. That is the biggest number that divides evenly into both a and b with nothing left over. For example, the biggest number that goes cleanly into both 12 and 8 is 4. The second is the LCM, short for Least Common Multiple. That is the smallest number that both a and b divide into evenly, in other words the smallest number that is on both of their times tables. The clever trick for the GCD is an old method called the Euclidean algorithm. Think of it like this: keep the smaller number and replace the bigger number with the remainder you get from dividing the bigger by the smaller. A remainder is just what is left over after a division, like how 13 divided by 5 leaves 3. Repeat until the remainder hits 0, and the other number sitting there is your GCD. Once you have the GCD, the LCM falls out of a simple formula: (a times b) divided by the GCD.

easyMathMath & Number TheoryTime: O(log(min(a,b))) · Space: O(1)

Signals to notice

GCD and LCMEuclidean algorithmrepeated remainder

Brute force first

Try all divisors — O(min(a,b)).

The key insight

gcd(a,b) = gcd(b, a%b). LCM = a / gcd × b. O(log min(a,b)).

Trace it on `a=12, b=8`

start gcd: a=12, b=8 (b!=0, keep going)
step: a,b = 8, 12%8=4  -> a=8, b=4 (b!=0)
step: a,b = 4, 8%4=0   -> a=4, b=0 (b==0, stop)
gcd loop ends, return a=4  => GCD=4
LCM = a/g*b = 12/4*8 = 3*8 = 24
return [GCD, LCM] = [4, 24]

What must stay true

Any common divisor of a and b also divides their remainder. The algorithm shrinks by at least half each step.

Shape of the loop

function gcd(a, b):
    while b != 0:
        a, b = b, a % b      // remainder shrinks the pair
    return a                  // last nonzero value is the GCD
g = gcd(a, b)
return [g, a / g * b]         // LCM; divide first to avoid overflow

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

LCM overflow — compute a/gcd × b instead of a×b/gcd.

Math & Number Theory Pattern