# Greatest Common Divisor

The **greatest common divisor (gcd)** of a set of integers is the largest integer that divides each integer in the set.

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

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 \\ 28: &1, 2, 4, 7, 14, 28 \end{align} \] The largest number that appears on every list is \( 2,\) so this is the greatest common divisor: \( \gcd(30,36,28)=2.\)

The gcd is a fundamental concept in number theory, and is taught to elementary school students as an aid to reducing fractions: dividing the top and bottom of a fraction \(\frac{a}{b}\) by the gcd of \(a,b\) will put it in lowest terms.

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

By listing divisors as above (or via other methods--see below), it can be shown that the greatest common divisor of \(246\) and \(642\) is \(6.\) Divide the top and bottom by \( 6\) to get \( \frac{41}{107}.\) This fraction is in lowest terms, because the only positive integer that divides both \( 41\) and \( 107\) is \(1.\)

The GCDs in this example are written \( \gcd(246,642)=6\) and \(\gcd(41,107)=1.\)

Pairs of integers, such as \(41\) and \(107,\) whose gcd is \( 1\) are called relatively prime.

The gcd is important for multiplication in modular arithmetic, and is essential in applications of elementary number theory, including RSA encryption and algorithms for factoring large integers.

## Computing the gcd

The example in the introduction was computed by listing the positive divisors of each number and searching for the largest number that appeared in every list. This is a very ineffective way to compute the gcd in general.

If the prime factorization of the numbers in the list is known, then computing the greatest common divisor is much simpler. The primes in the factorization of the gcd are the primes that appear in the factorizations of every number in the list, and their exponent in the gcd is the minimum of the exponents that appear in the factorizations in the list.

Compute \( \gcd(4200,3780,3528)\) using prime factorizations.

\[ \begin{align} 4200 &= 2^3 \cdot 3 \cdot 5^2 \cdot 7 \\ 3780 &= 2^2 \cdot 3^3 \cdot 5 \cdot 7 \\ 3528 &= 2^3 \cdot 3^2 \phantom{\cdot 5 \cdot} \cdot 7^2 \end{align} \] The gcd can be read off from these factorizations by using the smallest power of each prime that appears everywhere. This is \( 2^2 \cdot 3 \cdot 7 = 84.\)

Generalizing this example, 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} \] 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.

## Properties of the gcd

The gcd has many important properties which follow from divisibility rules and properties of the integers.

- The gcd of a list of numbers is
*divisible by*any other common divisor.

This is clear from the description using prime factorizations.

- Bezout's identity: \( \gcd(a,b)\) is the smallest positive integer that can be written in the form \(ax+by\) for some integers \(x,y.\)

This is an important identity for computing multiplicative inverses in modular arithmetic (and, more generally, for exploring the ideals of the positive integers and other rings).

- The gcd of a list of numbers can be computed two at a time, e.g. \( \gcd(a,b,c) = \gcd(\gcd(a,b),c).\)

So algorithms for computing the gcd can concentrate on the gcd of two numbers, since the gcd of a larger list can be reduced to the computation of the gcds of several pairs of numbers.

- \( \gcd(a,b) = \gcd(a-bq,b)\) for any integer \(q.\)

This fact is used repeatedly in the Euclidean algorithm (see below) to simplify the computation of the gcd.

- If \(a|bc\) and \( \gcd(a,b) =1,\) then \( a|c.\)

This is an important fact related to unique factorization. It follows from Bezout's identity: write \(ax+by=1,\) so \( acx+bcy=c,\) and \(a\) divides both terms on the left side, so it must divide the right side.

## Euclidean Algorithm

For large numbers, it is often difficult and time-consuming to compute prime factorizations. There is a very efficient method called the Euclidean Algorithm which computes the gcd of two integers without requiring their prime factorizations. The key fact that it uses is the identity \( \gcd(a,b) = \gcd(a-bq,b)\) for any integer \(q.\) This allows for the numbers \(a,b\) to be reduced recursively by successive divisions without changing the gcd. See the wiki for details.

## Problem Solving

How many ordered pairs of integers \( (a,b) \) are there, such that \( 100 \leq a \leq 1000, 100 \leq b \leq 1000 \) and

\[ \frac{a}{b} = \frac{12}{21}? \]

**Details and assumptions**

For an **ordered pair of integers** \((a,b)\), the order of the integers matter. The ordered pair \((1, 2)\) is different from the ordered pair \((2,1) \).

**Cite as:**Greatest Common Divisor.

*Brilliant.org*. Retrieved from https://brilliant.org/wiki/greatest-common-divisor/