Definition 1.6.8

A natural number $d$ is the greatest common divisor of nonzero integers $m$ and $n$ if

$d$ divides $m$ and $n$ and
whenever $x \in \mathbf{N}$ divides $m$ and $n$, then $x$ also divides $d$

The greatest common is unique if it exists by 1.6.2 (why?)

Proposition 1.6.9

For integers $n$ and $m$, let $$ \begin{align*} I(m,n) = \{am + bn \ | \ a, b \in \mathbf{Z}\}. \end{align*} $$

For $x, y \in I(m,n)$, $x + y \in I(m,n)$ and $-x \in I(m,n)$.
For all $x \in \mathbf{Z}$, $xI(m,n) \subseteq I(m,n)$.
If $b \in \mathbf{Z}$ divides $m$ and $n$, then $b$ divides all elements of $I(m,n)$.

Proof
Suppose $x, y \in I(m,n)$, then $x = am + bn$ for some $a$ and $b$ in $\mathbf{Z}$ and $y = cm + dn$ for some $c$ and $d$ in $\mathbf{Z}$. Therefore

$$ \begin{align*} x + y &= am + bn + cm + dn \\ &= (a+c)m + (b+d)n \end{align*} $$

And so $x+y \in I(m,n)$. $\ \blacksquare$
$(b)$ and $(c)$ have similar proofs.

Lemma 1.6.10

Let $m$ and $n$ be nonzero integers. If a natural number $d$ is a common divisor of $m$ and $n$ and an element of $I(m,n)$, then $d$ is the greatest common divisor of $m$ and $n$.

Proof
For any common divisor $x$ of $m$ and $n$, $x$ divides every element of $I(m,n)$ by proposition 1.6.9(c) and in particular it divides $d$. $\ \blacksquare$

Notes: $d$ is an element of $I(m,n)$. Therefore, $d = am + bn$. For any other common divisor $x$, $x$ divides every element of $I(m,n)$ so $x$ divides $d$ and we can write $d = am + bn = qx$.

Finding the Greatest Common Division

Suppose $m, n \in \mathbf{N}$ and suppose without the loss of generality that $|m| \geq |n|$. Let $q$ and $r$ be the quotient and remainder when dividing $m$ by $n$

$$ \begin{align*} m &= nq_1 + r_1 \\ n &= r_1q_2 + r_2 \\ r_1 &= r_2q_3 + r_3 \\ \vdots \\ r_{n-3} &= r_{n-2}q_{n-1} + r_{n-1} \\ r_{n-2} &= r_{n-1}q_{n} + 0 \end{align*} $$

In the case where $n_1 > 0$, then define again $q_2$ and $n_2$ such that

$$ \begin{align*} n &= q_2n_1 + n_2 \quad (\text{where } 0 \leq n_2 < n_1) \\ \end{align*} $$

Proposition 1.6.11

The natural number $r_{n-1}$ is the greatest common divisor of $m$ and $n$ and furthermore $r_{n-1} \in I(m,n)$

Proof
We first need to show that this process terminates. Observe that the sequence $\{r_1,r_2,...,r\} \in \mathbf{N}$ is decreasing so it truncates say at $r_{n-1}$ (the last non-zero element of the sequence). So it must terminates by the well ordering principle.

Next, we need to show that $r_{n-1}$ divides both $m$ and $n$. Observe that from the algorithm above that

$$ \begin{align*} r_{n-2} &= r_{n-1}q_{n} \end{align*} $$

This shows that $r_{n-1}| r_{n-2}$. Looking at the equation above this one, we see

$$ \begin{align*} r_{n-3} &= r_{n-2}q_{n} + r_{n-1} \end{align*} $$

And combining this with the previous conclusion that $r_{n-1} | r_{n-2}$, we see that $r_{n-1}| r_{n-3}$. If we continue this process, we will see that $r_{n-1}|a$ and $r_{n-1}|b$.

Finally, we need to show that $r_{n-1}$ is the greatest common divisor. So let $d$ be a common divisor of $m$ and $n$. So that $d | m$ and $d | n$. Using the first equation in the algorithm above,

$$ \begin{align*} m = nq + r_1 \end{align*} $$

we see that since $d$ divides both $m$ and $n$. Then it must divide $r_1$. Continuing with the second equation, we can see that $d$ divides $r_2$. Eventually, we can conclude that $d|r_{n_1}$. Since $d$ is arbitrary and $r_{n-1}$ is a common divisor, then $r_{n-1}$ must the greatest common divisor by definition. $\ \blacksquare$

TODO: Proof from the book

Corollary 1.6.11

Let $m$ and $n$ be nonzero integers, and write $d = gcd(m,n)$. Then

$d$ is the least element of $\mathbf{N} \cap I(m,n)$.
$I(m,n) = \mathbf{Z}d$, the set of all integers multiples of $d$

Proof
TODO

[1.6] Greatest Common Divisor (1.6.8 - 1.6.13)

Finding the Greatest Common Division

References