GCD and the Euclidean Algorithm

Finding Common Structure

The greatest common divisor $\gcd(a, b)$ is the largest positive integer dividing both $a$ and $b$. For $\gcd(12, 18) = 6$, since 6 divides both and nothing larger does. Its partner, the least common multiple $\operatorname{lcm}(a, b)$, is the smallest positive integer that both $a$ and $b$ divide. These govern fraction arithmetic, tiling problems, and modular equations.

You could compute the gcd from prime factorizations (take the lower power of each shared prime), but the Euclidean algorithm is far faster and needs no factoring. It rests on a single fact: $\gcd(a, b) = \gcd(b, r)$ where $r$ is the remainder of $a$ divided by $b$. Repeatedly replace the pair by (divisor, remainder) until the remainder is 0; the last nonzero remainder is the gcd. For $\gcd(48, 18)$: $$48 = 2 \cdot 18 + 12, \quad 18 = 1 \cdot 12 + 6, \quad 12 = 2 \cdot 6 + 0 \;\Rightarrow\; \gcd = 6.$$ This terminates quickly because the remainders shrink rapidly — it is one of the oldest and most elegant algorithms known.

Two numbers are coprime (relatively prime) when $\gcd(a, b) = 1$ — they share no prime factor. Coprimality is central to modular arithmetic (a number has a multiplicative inverse mod $n$ exactly when it is coprime to $n$).

A beautiful identity links gcd and lcm: $\gcd(a, b) \cdot \operatorname{lcm}(a, b) = a \cdot b$. So once you have the gcd (fast via Euclid), the lcm is just $\frac{ab}{\gcd(a,b)}$ — you never need to factor to find either.

Common pitfall: confusing the gcd (greatest common divisor, a factor of both) with the lcm (least common multiple, a multiple of both). The gcd is at most the smaller number; the lcm is at least the larger. For 12 and 18, gcd = 6 (small) and lcm = 36 (large) — mixing them up inverts the relationship. Remember $\gcd \cdot \operatorname{lcm} = ab$.