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.

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$.

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.

## 0 komentar

## Post a Comment