The Greatest Common Divisor

In this section we define the greatest common divisor (GCD) of two integers and discuss its properties. We also prove that the greatest common divisor of two integers is a linear combination of these integers. Two integers $a$ and $b$, not both 0, can have only finitely many divisors, and thus can have only finitely many common divisors. In this section, we are interested in the greatest common divisor of $a$ and $b$. Note that the divisors of $a$ and that of $|a|$ are the same.

Definition 1. The greatest common divisor of two integers $a$  and $b$ is the greatest integer that divides both $a$ and $b$. We denote the greatest common divisor of two integers $a$ and $b$ by $(a, b)$. We also define $(0, 0) = 0$.

Example.
Note that the greatest common divisor of 24 and 18 is 6. In other words (24, 18) = 6.

There are couples of integers (e.g. 3 and 4, etc...) whose greatest common divisor is 1 so we call such integers relatively prime integers.

Definition 2. Two integers $a$ and $b$ are relatively prime if $(a, b) = 1$. Example. The greatest common divisor of 9 and 16 is 1, thus they are relatively prime. Note that every integer has positive and negative divisors. If $a$ is a positive divisor of $m$, then $-a$ is also a divisor of m. Therefore by our definition of the greatest common divisor, we can see that $(a, b) = (| a |, | b |)$. We now present a theorem about the greatest common divisor of two integers. The theorem states that if we divide two integers by their greatest common divisor, then the outcome is a couple of integers that are relatively prime.

Theorem 1. If $(a, b) = d$ then $ ( \frac{a}{d},  \frac{b}{d}) = 1 $.

Proof. We will show that $ \frac{a}{d}$ and $\frac{b}{d}$ have no common positive divisors other than 1. Assume that $k$ is a positive common divisor such that $k | \frac{a}{d}$ and $k | \frac{b}{d}$. As a result, there are two positive integers $m$ and $n$ such that $ \frac{a}{d} = km$ and $ \frac{a}{d}= kn$. Thus we get that $a = kmd $ and $b = knd$. Hence $kd$ is a common divisor of both $a$ and $b$. Also, $kd \ge d$. However, $d$ is the greatest common divisor of $a$ and $b$. As a result, we get that $k = 1$.

The next theorem shows that the greatest common divisor of two integers does not change when we add a multiple of one of the two integers to the other.

Theorem 2. Let $a$, $b$ and $c$ be integers. Then $(a, b) = (a + cb, b)$.

Proof. We will show that every divisor of $a$ and $b$ is also a divisor of $a + cb$  and $b$ and vise versa. Hence they have exactly the same divisors. So we get that the greatest common divisor of a and b will also be the greatest common divisor of $a + cb$ and $b$. Let $k$ be a common divisor of $a$ and $b$. By Theorem 4, $k | (a + cb) $ and hence $k$ is a divisor of $a + cb$. Now assume that l is a common divisor of $ a + cb$ and $b$. Also by Theorem 4 we have , $l | ((a + cb) - cb) = a$. As a result, l is a common divisor of $a$ and $b$ and the result follows.

Example.
Notice that $(4, 14) = (4, 14 - 3 · 4) = (4, 2) = 2$.

We now present a theorem which proves that the greatest common divisor of two integers can be written as a linear combination of the two integers.

Theorem 3. The greatest common divisor of two integers $a$ and $b$, not both 0 is the least positive integer such that $ma + nb = d$ for some integers $m$ and $n$.

Proof. Assume without loss of generality that $a$ and $b$ are positive integers. Consider the set of all positive integer linear combinations of $a$ and $b$. This set is non empty since $a = 1 · a + 0 · b$ and $b = 0 · a + 1 · b$ are both in this set. Thus this set has a least element $d$ by the well-ordering principle. Thus $d = ma + nb$ for some integers $m$ and $n$. We have to prove that d divides both a and b and that it is the greatest divisor of $a$ and $b$. By the division algorithm, we have 

$a = dq + r$,  $0 \ge r < d $.

Thus we have $r = a - dq = a - q(ma + nb) = (1 - qm)a - qnb$.

We then have that $r$ is a linear combination of a and b. Since $0 \ge r < d $ and $d$ is the least positive integer which is a linear combination of $a$  and $b$, then $r = 0$ and $a = dq$. Hence $d | a$. Similarly $d | b$. Now notice that if there is $a$ divisor $c$ that divides both $a$ and $b$. Then $c$ divides any linear combination of $a$ and $b$ by a before Theorem . Hence $c | d$. This proves that any common divisor of $a$ and $b$ divides $d$. Hence $0 \ge r < d $, and $d$ is the greatest divisor. As a result, we conclude that if $(a, b) = 1$ then there exist integers m and n such that $ma + nb = 1$.

Defnition 3. Let $a_1$, $a_2$, ..., $a_n$ be integers, not all 0. The greatest common divisor of these integers is the largest integer that divides all of the integers in the set. The greatest common divisor of $a_1$, $a_2$, ..., an is denoted by $(a_1, a_2, ..., a_n)$.

Definition 4. The integers $a_1$, $a_2$, ..., $a_n$ are said to be mutually relatively prime if $(a_1, a_2, ..., a_n) = 1$.

Example. The integers 3, 6, 7 are mutually relatively prime since (3, 6, 7) = 1 although (3, 6) = 3.

Definition 5. The integers $a_1$, $a_2$, ..., $a_n$ are called pairwise prime if for each $i = j$, we have $(a_i, a_j ) = 1$.

Example. The integers 3, 14, 25 are pairwise relatively prime. Notice also that these integers are mutually relatively prime. Notice that if $a_1$, $a_2$, ..., $a_n$ are pairwise relatively prime then they are mutually relatively prime.

Share :