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, ..., a|bn 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 Divisor

Defn: The greatest common divisor, 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). (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, 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 with 0<r<l and
r = a-lq
= a-q(ax0+by0)
= a(1-qx0) + b(-y0)
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.

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: 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(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]

6. Linear Diophantine Equations

Consider problems of the form ax+by=c, where a,b,cZ are constants, and x,yZ 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:

1. 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)
2. 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.
1. Use the Extended Euclidean Algorithm to compute values {x,y} such that a'x+b'y=g.
2. Compute {x0, y0}:={x(c'/g), y(c'/g)}. This is a solution of the equation.
3. All solutions of the equation have the form {x0 + n(b/g), y0 - n(a/g)}, where nZ.

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

proof: ax+by=cax+by-c=0
g(ax+by-c)=0
gax+gby-gc=0
gax+gby=gc

Examples:

1. 6x+15y = 5
Note that gcd(6,15)=3, so 3 will divide 6x+15y for any integer values {x,y}.
But, 3 does not divide 5, so this equation has no solution.
2. 6x+15y = 9
• As gcd(6,15,9)=3, this equation has the same solutions as 2x+5y = 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 {x0, y0} = {(3)(-2),(3)(1)} = {-6,3} is a solution to the equation.
• And {xn, yn} = {-6+5n,3-2n} = {...,(-11,5),(-6,3),(-1,1),(4,-1),...} is the set of all solutions.

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