GCD and LCM

Finding the Greatest Common Divisor (GCD) and Least Common Multiple (LCM) is a common task.

GCD via Euclid's Algorithm: To find GCD(a, b) with $a < b$, find the remainder when $b$ is divided by $a$, let's call it $r_1$. Now, GCD(a, b) = GCD($r_1$, a). Repeat this process until the remainder is 0. The last non-zero remainder is the GCD. For example, GCD(36, 60) $\rightarrow$ GCD(24, 36) $\rightarrow$ GCD(12, 24) = 12.

LCM Formula: Once the GCD is known, the LCM can be found easily using the formula: $LCM(a, b) = \frac{a \times b}{GCD(a, b)}$.

For example, $LCM(36, 60) = \frac{36 \times 60}{12} = 3 \times 60 = 180$.