# The Greatest Common Divisors

:::info
**Definition (Greatest Common Divisor)**
Given two non-zero integers $a$ and $b$, the *greatest common divisor* of $a$ and $b$ (denoted as $\textrm{gcd}(a,b)$) is the largest integer that divides both $a$ and $b$.

$$
\textrm{gcd}(a,b) =\max\{d \in \mathbb{Z}: d \mid a \ \text{and} \ d \mid b\}
$$

If $\textrm{gcd}(a,b)=1$, we say that $a$ and $b$ are *relatively prime* to each other.
:::

:::warning
**Example**
1. For $a=24$ and $b=84$, the common divisors are $\pm1,\pm2,\pm3,\pm4,\pm6$ and $\pm12$. The greatest among these is $12$. Hence, $\textrm{gcd}(24,84)=12$.
2. For $a=25$ and $b=42$, the only common divisors are $\pm1$. The greatest among these is $1$. Hence, $\textrm{gcd}(25,42)=1$, and $25$ and $42$ are relatively prime.
:::

## Key Properties and Theorems
The following statements are proven theorems or propositions in number theory. While a **theorem** is a major result, a **proposition** is often a less significant true statement, and a **corollary** is a simple deduction from a theorem.

:::danger
**Theorem** If $a,b$ be integers with $\textrm{gcd}(a,b)=d$, then $\textrm{gcd}(\frac{a}{d},\frac{b}{d})=1$.
:::

:::danger
**Theorem** Let $a$, $b$ and $c$ be integers. Then $\textrm{gcd}(a+cb,b) = \textrm{gcd}(a,b)$.
:::

::: danger
**Proposition** For integers $a$ and $b$, and any integer $c$, the following properties hold:
* $\textrm{gcd}(a,b)=\textrm{gcd}(b,a)=\textrm{gcd}(\pm a,\pm b)$.
* If $a>0$, then $a=\textrm{gcd}(a,b) \Leftrightarrow a \mid b$.
:::

### Bézout's Identity
:::danger
**Theorem** (Bezout's Identity)
If $a$, $b$ be integers, there exist integers $m$ and $n$ such that $ma+nb = \textrm{gcd}(a,b)$.
:::

:::danger
**Corollary** The greatest common divisor of $a$ and $b$ is the smallest positive value of a linear combination of $a$ and $b$.

$$
\textrm{gcd}(a,b) = \min\{d \in \mathbb{Z}_+:d=ma+nb \;\textrm{for some}\; m,n \in \mathbb{Z} \}
$$
:::

:::warning
**Example** The set of all linear combinations of $9$ and $15$ is
$$
\{9m + 15n: m,n \in \mathbb{Z} \} = \{3k: k \in \mathbb{Z} \}
$$

* Since $\textrm{gcd}(9,15)=3$, Bézout's Identity tells us this set is equivalent to the set of all multiples of $3$, i.e., $\{3k:k \in \mathbb{Z}\}$.
* We can find a specific linear combination that equals 3, for example: $$3 = 9 \cdot 2 + 15 \cdot -1$$
:::

:::danger
**Theorem (Euclid's Lemma)** If $a,b,c$ are integers such that $a∣bc$ and $\textrm{gcd}(a,b)=1$, then $a∣c$.
:::

::: danger
**Proposition** If $d=\textrm{gcd}(a,b)$, then $dm = \textrm{gcd}(am,bm)$ for any $m \in \mathbb{N}$.
:::

:::success
**Exercise**
1. Find the greatest common divisor of each of the following pairs of integers.
* a) (15, 35)
* b) (0, 111)
* c) (−12, 18)
* d) (99, 100)
* e) (11, 121)
* f) (100, 102)
2. Let $a$ be a positive integer. What is the greatest common divisor of $a$ and $2a$?
3. Let $a$ be a positive integer. What is the greatest common divisor of $a$ and $a^2$?
4. Show that the greatest common divisor of an even number and an odd number is odd.
5. Show that if $a$ is an even integer and $b$ is an odd integer, then $\textrm{gcd}(a, b) = \textrm{gcd}(a/2, b)$.
:::

## The Euclidean Algorithm
The **Euclidean algorithm** is an efficient method for computing the greatest common divisor of two integers. It is based on the following property:

:::danger
**Theorem**
Given positive integers $a$ and $b$ with $a>b$. If we divide $a$ by $b$ to get $a=qb+r$, then $\textrm{gcd}(a,b) = \textrm{gcd}(b,r)$.
:::

To find $\textrm{gcd}(a,b)$, let $r_0 = a$ and $r_1 = b>0$. We repeatedly apply the division algorithm to get a sequence of remainders:

$$
r_{k-1} = r_{k} q_{k} + r_{k+1}
$$

The last non-zero remainder in this sequence is the greatest common divisor. We have:

$$
\textrm{gcd}(a,b) = \textrm{gcd}(r_1,r_2) = \ldots = \textrm{gcd}(r_{n-1},r_n) = r_n
$$

:::warning
**Example** Find $\textrm{gcd}(252,198)$ using the Euclidean algorithm and then express it as a linear combination of $252$ and $198$.

1. Use the Euclidean Algorithm to find the GCD: \begin{align} 252 &=198 \cdot 1+54 \\ 198 &=54\cdot 3 +36 \\ 54 &= 36 \cdot 1 + 18 \\ 36 &= 18 \cdot 2 \end{align} The last non-zero remainder is $18$, so $\textrm{gcd}(252,198)=18$.
2. Use the equations to work backwards and find the linear combination:
* Start with the second to last equation and solve for the remainder: $$18 = 54 - 36 \cdot 1$$
* Substitute the expression for $36$ from the line above it ($36=198−54 \cdot 3$): \begin{align} 18 &= 54 - (198−54 \cdot 3) \cdot 1 \\ &= 4 \cdot 54 − 1 \cdot 198 \end{align}
* Substitute the expression for $54$ from the top line ($54=252−198 \cdot 1$): \begin{align} 18 &= 4 \cdot (252 − 198 \cdot 1) − 1 \cdot 198 \\ &= 4 \cdot 252 − 5 \cdot 198\end{align}
* So, we have expressed $18$ as a linear combination: $18=4(252)+(−5)(198)$.
:::

:::success
**Exercise**

6. Use the Euclidean algorithm to find each of the following greatest common divisors.
* a) $\textrm{gcd}(45, 75)$
* b) $\textrm{gcd}(102, 222)$
* c) $\textrm{gcd}(666, 1414)$
* d) $\textrm{gcd}(20785, 44350)$
7. For each pair of integers in Exercise 6, express the greatest common divisor as a linear combination of these integers.
:::

## Extending the Definition of GCD
:::info
**Definition**
We can extend the definition of the greatest common divisor to more than two integers. Given integers $a_1,\ldots, a_n \in \mathbb{Z}$ that are not all zero, we define the greatest common divisor as:
$$
\textrm{gcd}(a_1, \ldots ,a_n) =
\max \{d \in \mathbb{Z} : d\mid a_1,\ldots,d\mid a_n\}
$$

If $\textrm{gcd}(a_1,\ldots,a_n)=1$, then we say $a_1,\ldots,a_n$ are mutually *relative prime*.
:::

:::danger
**Proposition** Let $a_1,\ldots, a_n$ be integers, not all equal to $0$. Then $\textrm{gcd}(a_1,\ldots, a_n)$ is the *smallest positive integer* that can be written as a *linear combination* of the numbers $a_1, \dots, a_n$ with integer coefficients.

That is, it's the smallest positive integer of the form:
$$
x_1 a_1 + x_2 a_2 + \dots + x_n a_n \quad \text{where} \ a_i \in \mathbb{Z}
$$
:::

:::danger
**Corollary** Let $a_1,\ldots, a_n$ be integers, not all equal to $0$.

* Every common divisor of $a_1,\ldots, a_n$ must also divide $\textrm{gcd}(a_1,\ldots, a_n)$.
* For each positive integer $m$, we have that $$\textrm{gcd}(m a_1,\ldots, m a_n) = m \cdot \textrm{gcd}(a_1,\ldots, a_n)$$
:::

:::danger
**Theorem** Given integers $a_1,\ldots, a_n$ that are not all zero, the GCD can be computed iteratively:
$$
\textrm{gcd}(a_1,\ldots , a_n) = \textrm{gcd}\left(a_1,\ldots ,\textrm{gcd}(a_{n-1}, a_n)\right)
$$
:::

:::warning
**Example**
1. $\textrm{gcd}(15,21,35) = \textrm{gcd}(15,\textrm{gcd}(21,35))=\textrm{gcd}(15,7) =1$
2. $\textrm{gcd}(105,140,350) = \textrm{gcd}(105,\textrm{gcd}(140,350))=\textrm{gcd}(105,70) =35$
:::

:::success
**Exercise**

8. Find the greatest common divisor of each of the following sets of integers.
* a) $(6, 10, 15)$
* b) $(70, 98, 105)$
* c) $(280, 330, 405, 490)$
9. Express the greatest common divisor of each set of numbers in Exercise 8 as a linear combination of the numbers in that set.
10. Find a set of three integers that are mutually relatively prime, but any two of which are not relatively prime. Do not use examples from the text.
:::