89 lines
2.9 KiB
XML
89 lines
2.9 KiB
XML
= 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.~◻
|
||
|
||
]
|