- Divisibility
- Division Algorithm
- Greatest Common Denominator
- Euclidean Algorithm
- Extended Euclidean Algorithm & Bezout
- Linear Diophantine Equations

**Texts:** [JJ98, Chap 1]
[Rose96, Sect 1.1]

Results applicable in any ring (? domain, i.e. w/o zero divisors?)

**Defn:** `a` *divides* `b`
(denoted `a`|`b`) if there exists an element
`x` such that `b`=`ax`.
If `a` divides `b` we say that `a`
is a *divisor* of `b`.

**Thm:** (Properties of Divisibility)

`a`|`b`⇒`a`|`bc``a`|`b`and`b`|`c`⇒`a`|`c``a`|`b`and`a`|`c`⇒ ∀`x`,`y`,`a`|(`bx`+`cy`)`a`|`b`and`b`|`a`⇒`a`=±`b`(in general,`a`and`b`are associates)`a`|`b`,`a`>0,`b`>0 ⇒`a`≤`b`(can be generalized to rings with Euclidean norms)`m`≠0 ⇒ (`a`|`b`⇔`ma`|`mb`)`a`|`b`_{1}, ...,`a``b`_{n}and`u`_{i}}⊂**Z**⇒`a`|(`u`_{1}`b`_{1}+...+`u`_{n}`b`_{n})

**proof:**

- ∃
`x`such that`b`=`ax`

so`bc`=`axc`

so`bc`=`a`(`cx`) and`a`|`bc` - similar
- ∃
`z`and`w`such that`b`=`az`and`c`=`aw`

so`bx`+`cy`=`azx`+`awy`=`a`(`zx`+`wy`)

so`a`|`bx`+`cy` - note that the absolute value of any integer (other than zero) is greater than or equal to one and absolute value respects multiplication (also true in integral domains)
- ⇒: similar to (
*i*)

⇐: We first prove the cancellation law:`ma`=`mb`⇒`a`=`b`

`ma`=`mb`⇒`m`(`a`-`b`)=0

but`m`(`a`-`b`)=0 ⇒`m`=0 or`a`=`b`(the sticky step)

but as`m`≠0 we must have`a`=`b`

now apply this and the same methods as in (*i*)

(true in any integral domain, or any ring if we require that`m`not be a zero divisor) - obvious extension of (
*iii*)

**Thm:** (Division Algorithm) Given `a`, `b` with
`a`>0 there are unique `q` and `r` such that
`b`=`qa`+`r``r`<`a``a` does not divide `b` then `r`≠0.

**Well-Ordering Property of Z**: If some subset of the natural
number is non-empty, C⊆**N**, then C has a least element.
Note that this property does not hold in this form for **Z**,
**Q** or **R**.

**Thm:** If `a` and `b` are positive integers
then there exist unique integers `q` and `r` such
that `a`=`qb`+`r` and
0≤`r`<`b`.

**proof:** Consider the set of integers
{..., `a`+2`b`, `a`+`b`,
`a`, `a`-`b`,
`a`-2

Of these, only consider the positive elements.

This set has a smallest element, `a`-`qb`

Call this smallest element `r` ≥ 0
`r` < `b` as otherwise
`r`-`b` ≥ 0 would be a smaller element of
the set. Thus proves existence.

Now we prove uniqueness:

Assume that `a` = `qb`+`r` = `q`'`b`+`r`'

So `b`(`q`-`q`') = `r` - `r`'

If `q` ≠ `q`' then |`q`'-`q`| ≥ 1

so |`r`'-`r`|≥`b`

but |`r`'-`r`|<|`b`-0|=`b`,
which contradicts our minimality assumption as we saw above

Thus `q`=`q`' and `r`=`r`',
and we have uniqueness as desired.♠

We will see later that this simple algorithm is the keystone of classical number theory over the integers. While many other rings of interest also have a division algorithm, many do not, and that is where life gets "interesting".

**Defn:** The *greatest common denominator*, GCD, of two elements
`a` and `b` is an element `d` such that:

`d`|`a`and`d`|`b`- If
`c`|`a`and`c`|`b`then`c`≤`d`

We can easily show that the GCD exists, using the following
reasoning. The set of common divisors of two numbers
`a` and `b` is non-empty (1 is a common divisor).
The set of common divisors is bounded above by the least of
|`a`| and |`b`|. Thus we can apply the
well-ordering principle to the set of common divisors (strictly
speaking, rather than finding the maximal element of this set
we might have to find the minimal element of the set of their
negatives, but that is a minor detail).

**Thm:** (Bezout's Thm [a restricted form])
There exist `x` and `y` such that
gcd(`a`, `b`) = `ax`+`by`.

**proof:** Consider the set {`ax`+`by`
| `x`, `y` ∈ **Z**}

Choose `x`_{0}, `y`_{0}
so that `ax`_{0}+`by`_{0} is
the least positive element (well ordering again)

Call this element `l` = `ax`_{0}+`by`_{0}

We now prove that `l`|`a` and `l`|`b`

Assume the converse - that `l` does not divide

So ∃ `q`, `r` such that
`a` = `lq`+`r`, 0<`r`<`l`

So `r` = `b`-`lq`
= `b`-`q`(`ax`_{0}+`by`_{0})
= `b`(1- Arghh... notation

This of course gives us a proof that the gcd of two numbers and some linear combination of the numbers exists, but has no computational value. In a great number of rings we are left sitting here, knowing of the existence of the gcd but unable to practically compute it. The beauty of the integers (and a limited set of other useful rings) is that we have an efficient way of computing these values - the Euclidean Algorithm.

**Algorithm:** (Computing GCD(a,b)) [Euclidean Algorithm]

If a < b then swap a and b Repeat while b > 0 { q ← ⌊a/b⌋ (integer quotient of a and b) a ← a - qb swap a and b } (b is now equal to zero and a to the gcd) print "gcd is", a

**Examples:** Examples can be worked out with the script
found here

**Lemma:** `a`=`qb`+`r` ⇒
gcd(`a`,`b`)=gcd(`r`,`b`)
[JJ98, Lemma 1.5]

**proof:**

**Work:** [Knuth]

- Lower bound: gcd(
`N`,`N`+1) in one step - Upper bound: gcd(
`f`_{n+2},`f`_{n+1}) in`n`steps, where`f`_{n}≈(1/2+√5/2)^{n}/√5 [Lamé] (homework, [JJ98, SuppEx 1.17-1.21]) - "Avg" Case: (12 ln 2/π
^{2})ln`n`steps [Heilbronn]

**Generalizations:**

**Q**[`x`] - use degree as norm**Q**[`x`,`y`] - failure (various degree functions, but no division algorithm), partially replaced by Buchberger's algorithm

**[ScOp84]***From Fermat to Minkowski*, W. Scharlau & H. Opolka, Springer, 1984**[Still89]***Mathematics and its History*, J. Stillwell, Springer, 1989**[Weil83]**,*Number Theory*, A. Weil, Birkhäuser, 1983

Robert Campbell, campbell@math.umbc.edu 29 Dec, 2002