Lectures 2 & 3: Divisibility & Euclidean Algorithm, Math 413 (Number Theory)

# Lectures 2 & 3: Divisibility & Euclidean Algorithm

## 1. Divisibility

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)

1. a|ba|bc
2. a|b and b|ca|c
3. a|b and a|c ⇒ ∀x,y, a|(bx+cy)
4. a|b and b|aab (in general, a and b are associates)
5. a|b, a>0, b>0 ⇒ ab (can be generalized to rings with Euclidean norms)
6. m≠0 ⇒ (a|bma|mb)
7. a|b1, ..., abn and ui}⊂Za|(u1b1+...+unbn)

proof:

1. x such that b=ax
so bc=axc
so bc = a(cx) and a|bc
2. similar
3. z and w such that b=az and c=aw
so bx+cy = azx+awy = a(zx+wy)
so a|bx+cy
4. 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)
5. ⇒: similar to (i)
⇐: We first prove the cancellation law: ma=mba=b
ma=mbm(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)
6. obvious extension of (iii)

## 2. Division Algorithm

Thm: (Division Algorithm) Given a, b with a>0 there are unique q and r such that b=qa+r and 0≤r<a. If 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+2b, a+b, a, a-b, a-2b,...}
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 qq' 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".

## 3. Greatest Common Denominator

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

1. d|a and d|b
2. If c|a and c|b then cd

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, yZ}
Choose x0, y0 so that ax0+by0 is the least positive element (well ordering again)
Call this element l = ax0+by0
We now prove that l|a and l|b
Assume the converse - that l does not divide a
So ∃ q, r such that a = lq+r, 0<r<l
So r = b-lq = b-q(ax0+by0) = 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.

## 4. 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(fn+2, fn+1) in n steps, where fn≈(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
[MaWo03, EuclideanAlgorithm.html]

## References

[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