GCD and the Euclidean Algorithm

The greatest common divisor $\gcd(a, b)$ is the largest positive integer dividing both $a$ and $b$. Its partner, the least common multiple $\operatorname{lcm}(a, b)$, is the smallest positive integer that both $a$ and $b$ divide.

Factoring is slow for large numbers. The Euclidean algorithm finds $\gcd(a, b)$ instantly using the rule: $$\gcd(a, b) = \gcd(b, r)$$ where $r$ is the remainder of $a \div b$.

Repeatedly replace $(a, b)$ with $(b, r)$ until $r = 0$. The last nonzero remainder is the gcd. Here, $\gcd(48, 18) = 6$.

Coprime and the LCM Link

Two numbers are coprime (relatively prime) when $\gcd(a, b) = 1$, meaning they share no prime factors. This is essential for finding multiplicative inverses in modular arithmetic.

You can find the lcm instantly without factoring using the identity: $$\gcd(a, b) \cdot \operatorname{lcm}(a, b) = a \cdot b$$ Rearranging gives $\operatorname{lcm}(a, b) = \frac{ab}{\gcd(a,b)}$.

Common Pitfall: Never confuse the two terms: