- Divisibility
- Division Algorithm
- Greatest Common Divisor
- 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 divisor*, 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). (The GCD is sometimes
also called the *Greatest Common Factor*, GCF.)

**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 `a`

So ∃ `q`, `r` with 0<`r`<`l` and
`r` = `a-lq`

= `a`-`q`(`ax`_{0}+`by`_{0})

= `a`(1-`qx`_{0}) + `b`(-`y`_{0})

So `r` is a positive element of the set which is smaller than `l`#

Thus `l`|`a` and similarly `l`|`b`

So `l` | gcd(`a,b`)♠

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:** gcd(`a`,`b`-`a`)=gcd(`a`,`b`)
[JJ98, Lemma 1.5]
**proof:** g = gcd(a,b) ⇒ (g | a) and (g | b) ⇒ a = ng and b = mg for some n and m

So if a = qb + r then r = a - qb, so r = ng - qmg = g(n-qm)

So (g | r) ⇒ (g | gcd(r,b)), i.e. (gcd(a,b) | gcd(r,b))

Similarly, we can show that (gcd(r,b) | gcd(a,b))

Thus gcd(a,b) = ± gcd(r,b))

As both are positive, we have gcd(a,b) = gcd(r,b))♠

In more general rings we can still show that gcd(`a`,`b`)
and gcd(`a`-`qb`,`b`) are associates
(differ by a unit).

**Lemma:**
gcd(`a`,0)=`a`

**Theorem:** The Euclidean Algorithm produces gcd(`a`,`b`)

**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

Consider problems of the form `ax`+`by`=`c`, where
`a,b,c`∈**Z** are constants, and `x,y`∈**Z**
are the unknown variables. Finding integer solutions is equivalent to finding
integer points on a line with a rational slope and rational intercept.

**Algorithm: **An algorithm to find all solutions to `ax`+`by`=`c` is:

- Replace
`ax`+`by`=`c`with`a'x`+`b'y`=`c'`, where`a'`=`a`/gcd(`a,b,c`),`b'`=`b`/gcd(`a,b,c`) and`c'`=`c`/gcd(`a,b,c`) - Let
`g`:=gcd(`a',b'`). Does`g`divide c'?- No:
`g`does not divide c' ⇒ There are no solutions to the equation. - Yes:
`g`divides c' ⇒ The equation has solutions.- Use the Extended Euclidean Algorithm to compute values {
`x,y`} such that`a'x`+`b'y`=`g`. - Compute {
`x`_{0},`y`_{0}}:={`x(c'/g), y(c'/g)`}. This is a solution of the equation. - All solutions of the equation have the form {
`x`_{0}+`n`(`b/g`),`y`_{0}-`n`(`a/g`)}, where`n`∈**Z**.

- Use the Extended Euclidean Algorithm to compute values {

- No:

**Prop: ** {`x,y`} satisfies the equation `ax`+`by`=`c` iff it satisfies the equation `gax`+`gby`=`gc` (if `g`≠0)

**proof:** `ax`+`by`=`c` ⇔ `ax`+`by`-`c`=0

⇔ `g`(`ax`+`by`-`c`)=0

⇔ `gax`+`gby`-`gc`=0

⇔ `gax`+`gby`=`gc`

**Examples: **

- 6
`x`+15`y`= 5

Note that gcd(6,15)=3, so 3 will divide 6`x`+15`y`for any integer values {`x,y`}.

But, 3 does not divide 5, so this equation has no solution. - 6
`x`+15`y`= 9- As gcd(6,15,9)=3, this equation has the same solutions as 2
`x`+5`y`= 3 - The Extended Euclidean Algorithm allows us to compute gcd(2,5)=1 with coefficients {-2,1} (i.e. (2)(-2)+(5)(1)=1)
- Thus {
`x`_{0},`y`_{0}} = {(3)(-2),(3)(1)} = {-6,3} is a solution to the equation. - And {
`x`_{n},`y`_{n}} = {-6+5`n`,3-2`n`} = {...,(-11,5),(-6,3),(-1,1),(4,-1),...} is the set of all solutions.

- As gcd(6,15,9)=3, this equation has the same solutions as 2

**[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