Greatest Common Divisor

The greatest common divisor (GCD), also called the greatest common factor, of two numbers is the largest number that divides them both. For instance, the greatest common factor of 20 and 15 is 5, since 5 divides both 20 and 15 and no larger number has this property. The concept is easily extended to sets of more than two numbers: the GCD of a set of numbers is the largest number dividing each of them.

The GCD is used for a variety of applications in number theory, particularly in modular arithmetic and thus encryption algorithms such as RSA. It is also used for simpler applications, such as simplifying fractions. This makes the GCD a rather fundamental concept to number theory, and as such a number of algorithms have been discovered to efficiently compute it.

The GCD is traditionally notated as \(\text{gcd}(a, b)\), or when the context is clear, simply \((a, b)\).

The GCD of several numbers may be computed by simply listing the factors of each number and determining the largest common one. While in practice this is terribly inefficient, for particularly small cases it is doable by hand. The process may be split up using the method of factor pairs: once one determines a factor \(a\) of a number \(n\), the quotient \(\frac{n}{a}\) is necessarily a factor as well. For instance, since 2 is a factor of 24, \(\frac{24}{2} = 12\) is a factor as well.

Find the greatest common divisor of \( 30, 36,\) and \(24.\)

---

The divisors of each number are given by

\[ \begin{align} 30: &1, 2, 3, 5, 6, 10, 15, 30 \\ 36: &1, 2, 3, 4, 6, 9, 12, 18, 36 \\ 24: &1, 2, 4, 6, 12, 24 \end{align} \]

The largest number that appears on every list is \( 6,\) so this is the greatest common divisor:

\[ \gcd(30,36,24)=6.\ _\square\]

When the numbers are large, the list of factors can be prohibitively long making the above method very difficult. A somewhat more efficient method is to first compute the prime factorization of each number in the set. The resulting GCD is the product of the primes that appear in every factorization, to the smallest exponent seen in the factorizations. This is confusing in words, so let's see an example:

Compute \( \gcd(4200,3780,3528)\).

---

We have

\[\begin{align} 4200 &= 2^3 \cdot 3^{\phantom 1} \cdot 5^2 \cdot 7 \\ 3780 &= 2^2 \cdot 3^3 \cdot 5^{\phantom 1} \cdot 7 \\ 3528 &= 2^3 \cdot 3^2 \ \ \phantom{\cdot 5^0} \cdot 7^2. \end{align}\]

Since 2 appears in each of these factorizations, it will appear in the GCD as well. It is taken to the smallest power seen in the factorizations, which in this case is 2. So the GCD will contain \(2^2\) in its factorization. Continuing along these lines, we obtain a GCD of

\[ 2^2 \cdot 3 \cdot 7 = 84.\ _\square\]

In formal notation, if the prime factorizations of \(a\) and \(b\) are

\[a = p_1 ^{\alpha_1} p_2 ^{\alpha_2} \ldots p_k ^{\alpha_k}, \quad b = p_1 ^{\beta_1} p_2 ^ {\beta_2} \ldots p_k ^ {\beta_k},\]

where the \(p_i\) are distinct primes and the \(\alpha_i\) and \( \beta_i\) are nonnegative integers, then

\[ \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)} . \]

A similar formula holds for finding the GCD of several integers, by taking the smallest exponent for each prime.

While the prime factorization method is often the most practical to do by hand, occasionally determining the prime factorization is very difficult, in which case an alternate approach becomes necessary. Generally, in these cases, algorithms are used as in the next section.

Because large numbers are difficult to work with by hand, there are a number of algorithms used to simplify the problem down to a manageable level. Since the GCD has the property that

\[\text{gcd}(a, b, c) = \text{gcd}(\text{gcd}(a,b), c)\]

the GCD can be calculated "two at a time", e.g. if we wanted to find the GCD of 20, 28, and 24, we could first find the GCD of \(20\) and \(28\) (which is 4) and then the GCD of 4 and 24 (which is also 4). As a result, almost all algorithms focus on the simplest case of determining the GCD of two numbers.

The Euclidean algorithm is based on the following key observation: if \(d\) divides \(a\) and \(d\) divides \(b\), then \(d\) also divides \(a - b\) (via, for example, modular arithmetic). This means that the GCD of \(a\) and \(b\) is the same as the GCD of \(a - b\) and \(b\), which is progress since this makes the numbers smaller.

As a result, we can repeat this process to form an algorithm:

1. If \(a = b\), stop -- the GCD of \(a\) and \(a\) is, of course, \(a\). Otherwise, go to step 2.
2. If \(a > b\), replace \(a\) with \(a - b\), and go back to step 1.
3. If \(b > a\), replace \(b\) with \(b - a\), and go back to step 1.

Determine the greatest common factor of 84 and 132.

---

We follow our algorithm:

1. \(a\) is 84 and \(b\) is 132. Since \(b > a\), we replace \(b\) with \(b - a = 132 - 84 = 48\).
2. \(a\) is 84 and \(b\) is 48. Since \(a > b\), we replace \(a\) with \(a - b = 84 - 48 = 36\).
3. \(a\) is 36 and \(b\) is 48. Since \(b > a\), we replace \(b\) with \(b - a = 12\).
4. \(a\) is 36 and \(b\) is 12. Since \(a > b\), we replace \(a\) with \(a - b = 24\).
5. \(a\) is 24 and \(b\) is 12. Since \(a > b\), we replace \(a\) with \(a - b = 12\).
6. \(a\) is 12 and \(b\) is 12. Since \(a = b\), the GCD is 12.

Since the numbers get smaller at each point, this algorithm will eventually finish and produce the GCD. In practice this can be made rather efficient, as described in the main wiki page -- you may have noticed, for instance, that once we get to 36 and 12 we can "skip" the \(a = 24\) step. The Euclidean algorithm is especially useful by hand, since oftentimes the GCD will be become "obvious" by inspection once the numbers get low enough (e.g. you might have noticed at the \(a = 36, b = 12\) step that the GCD is 12 since \(36 = 12 \cdot 3\)).

There is additionally a slightly more complicated algorithm called Stein's algorithm, which is based on the same observation but additionally checks the parity of both numbers:

1. If \(a = b\), stop -- the GCD of \(a\) and \(a\) is, of course, \(a\). Otherwise, go to step 2.
2. If \(a\) and \(b\) are both even, replace \(a\) with \(\frac{a}{2}\), \(b\) with \(\frac{b}{2}\), and increment a counter.
3. If \(a\) is even and \(b\) is odd, replace \(a\) with \(\frac{a}{2}\).
4. If \(a\) is odd and \(b\) is even, replace \(b\) with \(\frac{b}{2}\).
5. If \(a\) and \(b\) are both odd, replace \(a\) with \(a - b\) (just like in the Euclidean algorithm above).

This is, for computers, somewhat more efficient since divisions-by-2 are very fast due to their use of binary numbers. It is also somewhat more natural to do by hand; essentially, if you notice "obvious" common factors at any point of the Euclidean algorithm (here, the "obvious" common factor is 2, but it can also be others using divisibility rules).

The GCD is used for a number of applications both simple and complex. In fact, you've likely implicitly calculated GCDs without recognizing it when simplifying fractions: reducing a fraction is a matter of dividing both the numerator and denominator by their GCD.

What is \( \frac{246}{642}\) in lowest terms?

---

By any of the above methods, we calculate the greatest common divisor of \(246\) and \(642\) to be \(6.\) Divide the top and bottom by \( 6\) to get \(\frac{41}{107}\). This fraction is indeed in lowest terms (as we expect), because the only positive integer that divides both \( 41\) and \( 107\) is \(1.\) \(_\square\)

Pairs of integers, such as \(41\) and \(107,\) whose gcd is \( 1\) are called relatively prime, and are useful for a number of reasons such as Bezout's identity.

The GCD is also used in the extended Euclidean algorithm to compute modular inverses, which are of extreme importance in encryption schemes such as RSA. It is additionally rather important when considering the order of an element, particularly in Lagrange's theorem especially as applied to modular arithmetic. This makes it a common topic in competitions and olympiads.