Waste less time on Facebook — follow Brilliant.

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
2 years, 2 months ago

No vote yet
1 vote


There are no comments in this discussion.


Problem Loading...

Note Loading...

Set Loading...