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 \).

## Comments

There are no comments in this discussion.