= Introduction
<introduction>
Let $a , b in bb(Z)$. We say that $a$ #strong[divides] $b$, written
$a divides b$, if there exists $c in bb(Z)$ such that $b = a c$.

#block[
#strong[Definition 1];. A positive integer $p > 1$ is called
#strong[prime] if its only positive divisors are $1$ and $p$ itself.

Hello
]
#block[
#strong[Definition 2];. For integers $a$ and $b$, not both zero, the
#strong[greatest common divisor] $gcd (a , b)$ is the largest positive
integer that divides both $a$ and $b$.

]
= The Euclidean Algorithm
<the-euclidean-algorithm>
The Euclidean algorithm is an efficient method for computing the
greatest common divisor of two integers.

#block[
#strong[Theorem 3] (Division Algorithm). #emph[Let $a , b in bb(Z)$ with
$b > 0$. Then there exist unique integers $q$ and $r$ such that
$ a = b q + r quad upright("with") quad 0 lt.eq r < b . $ Here $q$ is
called the #strong[quotient] and $r$ is called the #strong[remainder];.]

]
#block[
#strong[Theorem 4];. #emph[If $a = b q + r$, then
$gcd (a , b) = gcd (b , r)$.]

]
#block[
#emph[Proof.] Let $d = gcd (a , b)$. Then $d divides a$ and
$d divides b$. Since $r = a - b q$, we have $d divides r$. Thus $d$ is a
common divisor of $b$ and $r$, so $d lt.eq gcd (b , r)$.

Conversely, let $d' = gcd (b , r)$. Then $d' divides b$ and
$d' divides r$. Since $a = b q + r$, we have $d' divides a$. Thus $d'$
is a common divisor of $a$ and $b$, so $d' lt.eq gcd (a , b) = d$.

Therefore $d = gcd (b , r)$.~◻

]
== The Algorithm
<the-algorithm>
To compute $gcd (a , b)$ where $a gt.eq b > 0$:

+ Apply the division algorithm repeatedly:
  $ a & = b q_1 + r_1 , quad 0 lt.eq r_1 < b\
  b & = r_1 q_2 + r_2 , quad 0 lt.eq r_2 < r_1\
  r_1 & = r_2 q_3 + r_3 , quad 0 lt.eq r_3 < r_2\
   & dots.v\
  r_(n - 2) & = r_(n - 1) q_n + r_n , quad 0 lt.eq r_n < r_(n - 1)\
  r_(n - 1) & = r_n q_(n + 1) + 0 $

+ The last non-zero remainder $r_n$ is $gcd (a , b)$.

#block[
#strong[Theorem 5] (Bézout’s Identity). #emph[Let $a , b in bb(Z)$, not
both zero, and let $d = gcd (a , b)$. Then there exist integers $x$ and
$y$ such that $ a x + b y = d . $]

]
#block[
#emph[Proof.] Consider the set
$S = { a x + b y : x , y in bb(Z) upright(" and ") a x + b y > 0 }$.
This set is non-empty (contains $lr(|a|)$ or $lr(|b|)$) and bounded
below by $1$, so by the well-ordering principle it has a smallest
element, say $d' = a x_0 + b y_0$.

We claim that $d' = gcd (a , b)$. First we show that $d' divides a$. By
the division algorithm, write $a = d' q + r$ with $0 lt.eq r < d'$. Then
$ r = a - d' q = a - (a x_0 + b y_0) q = a (1 - x_0 q) + b (- y_0 q) . $
If $r > 0$, then $r in S$ and $r < d'$, contradicting the minimality of
$d'$. Thus $r = 0$ and $d' divides a$. Similarly, $d' divides b$.

So $d'$ is a common divisor of $a$ and $b$, hence
$d' lt.eq d = gcd (a , b)$.

Conversely, since $d divides a$ and $d divides b$, we have
$d divides (a x_0 + b y_0) = d'$. Thus $d lt.eq d'$.

Therefore $d = d'$, completing the proof.~◻

]