×

# Greatest Common Divisor

The greatest common divisor of a set of integers is the largest number that divides each integer in the set. We denote the greatest common divisor by $$\gcd(a, b, \ldots)$$. We can attempt to find this value by listing all divisors of the integers and finding the largest divisor. However, such a procedure can get tedious.

If the prime factorizations of $$a$$ and $$b$$ are

\begin{align} a & = p_1 ^{\alpha_1} p_2 ^{\alpha_2} \ldots p_k ^{\alpha_k}, \\ b & = p_1 ^{\beta_1} p_2 ^ {\beta_2} \ldots p_k ^ {\beta_k}, \\ \end{align}

then the GCD of the numbers is equal to

$\gcd(a,b) = p_1 ^{\min(\alpha_1, \beta_1)} p_2 ^{\min(\alpha_2, \beta_2)} \ldots p_k ^{\min(\alpha_k, \beta_k)} .$

For example: $$\mbox{gcd}(12,18) = \mbox{gcd}(2^2 \cdot 3, 2 \cdot 3^2) = 2 \cdot 3 = 6$$.

Note by Arron Kau
3 years, 2 months ago