Greatest Common Divisor

The Greatest Common Divisor

Definition: Let $a, b \in \mathbb{Z}$. The Greatest Common Divisor of $a$ and $b$ denoted $(a, b)$ is the integer $d \in \mathbb{Z}$ such that:
1. $d \mid a$ and $d \mid b$.
2. If $c \in \mathbb{Z}$, $c \mid a$, and $c \mid b$ then $c \leq d$.
If $(a, b) = 1$ then the integers $a$ and $b$ are said to be Relatively Prime.

The first property in the definition above says that $d$ is a common divisor of $a$ and $b$, while the second property in the definition says that $d$ is the greatest of such divisors.

Notice that since $1$ divides all integers, we have that $(a, b) \geq 1$. Let's look through some quick examples. Suppose that we want to compute $(3, 21)$. For this example, $(3, 21) = 3$, since $3 \mid 3$ and $3 \mid 21$. Notice that all other divisors of $3$ and $21$ are less than or equal to $3$.

For another example, suppose we want to evaluate $(24, 56)$. It should be clear that $2 \mid 24$ and $2 \mid 56$ because $2(12) = 24$ and $2(28) = 56$. However, this just proves that $2$ divides both $24$ and $56$. We can find $8 \mid 24$ and $8 \mid 56$ as well, and $8 \geq 2$. In fact, there exists no integer greater than $8$ that divides both $24$ and $56$. Hence $(24, 56) = 8$.

Theorem 1: Let $a, b, d \in \mathbb{Z}$. If $(a, b) = d$ then $\left ( \frac{a}{d}, \frac{b}{d} \right ) = 1$.
  • Proof: Assume that the greatest common divisor of $\left ( \frac{a}{d}, \frac{b}{d} \right ) = c$ for some $c \in \mathbb{Z}$. Then $c \mid \frac{a}{d}$ and $c \mid \frac{b}{d}$.
  • By the definition of integer division, there must exist some $x \in \mathbb{Z}$ such that $cx = \frac{a}{d}$ and some $y \in \mathbb{Z}$ such that $cy = \frac{d}{d}$. Therefore:
(1)
\begin{align} cdx = a \quad \mathbf{and} \quad cdy = b \end{align}
  • However, notice that both a and b share a common divisor $cd$ and hence $cd \mid a$, and $cd \mid b$. The greatest common divisor $(a, b) = d$, so $cd \leq d$ and hence $c \leq 1$. But we always have that $c \geq 1$ and hence $c = 1$. $\blacksquare$
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License