3Division
IA Numbers and Sets
3.1 Euclid’s Algorithm
Definition
(Factor of integers)
.
Given
a, b ∈ Z
, we say
a
divides
b
,
a
is a factor
of
b
or
a | b
if (
∃c ∈ Z
)
b
=
ac
. For any
b
,
±
1 and
±b
are always factors of
b
.
The other factors are called proper factors.
Theorem
(Division Algorithm)
.
Given
a, b ∈ Z
,
b 6
= 0, there are unique
q, r ∈ Z
with a = qb + r and 0 ≤ r < b.
Despite the name, the division algorithm is not an algorithm in the usual
sense. Instead, it merely states that you can divide. Even the proof does not
specify a (non-brute force) way of how to divide.
Proof.
Choose
q
=
max{q
:
qb ≤ a}
. This maximum exists because the set of all
q
such that
qb ≤ a
is finite. Now write
r
=
a −qb
. We have 0
≤ r < b
and thus
q and r are found.
To show that they are unique, suppose that
a
=
qb
+
r
=
q
0
b
+
r
0
. We
have (
q − q
0
)
b
= (
r
0
− r
). Since both
r
and
r
0
are between 0 and
b
, we have
−b < r − r
0
< b
. However,
r
0
− r
is a multiple of
b
. Thus
q − q
0
=
r
0
− r
= 0.
Consequently, q = q
0
and r = r
0
.
Definition
(Common factor of integers)
.
A common factor of
a
and
b
is a
number c ∈ Z such that c | a and c | b.
Definition
(Highest common factor/greatest common divisor)
.
The highest
common factor or greatest common divisor of two numbers
a, b ∈ N
is a number
d ∈ N
such that
d
is a common factor of
a
and
b
, and if
c
is also a common
factor, c | d.
Clearly if the hcf exists, it must be the largest common factor, since all other
common factors divide it, and thus necessarily unique.
You might think reasonably it is more natural to define
hcf
(
a, b
) to be the
largest common factor. Then show that it has the property that all common
factors divide it. But the above definition is superior because it does not require
a prior ordering of the natural numbers (and can be extended to any ring even
if they are not ordered, as we will do in IB Groups, Rings and Modules).
Notation. We write d = hcf(a, b) = gcd(a, b) = (a, b).
Here we use (
a, b
) to stand for a number, and has nothing to do with an
ordered pair.
Proposition. If c | a and c | b, c | (ua + vb) for all u, v ∈ Z.
Proof.
By definition, we have
a
=
kc
and
b
=
lc
. Then
ua
+
vb
=
ukc
+
vlc
=
(uk + vl)c. So c | (ua + vb).
Theorem. Let a, b ∈ N. Then (a, b) exists.
Proof.
Let
S
=
{ua
+
vb
:
u, v ∈ Z}
be the set of all linear combinations of
a, b
.
Let
d
be the smallest positive member of
S
. Say
d
=
xa
+
yb
. Hence if
c | a, c | b
,
then c | d. So we need to show that d | a and d | b, and thus d = (a, b).
By the division algorithm, there exist numbers
q, r ∈ Z
with
a
=
qd
+
r
with
0
≤ r < d
. Then
r
=
a−qd
=
a
(1
−qx
)
−qyb
. Therefore
r
is a linear combination
of
a
and
b
. Since
d
is the smallest positive member of
S
and 0
≤ r < d
, we have
r = 0 and thus d | a. Similarly, we can show that d | b.
Corollary.
(from the proof) Let
d
= (
a, b
), then
d
is the smallest positive linear
combination of a and b.
Corollary
(B´ezout’s identity)
.
Let
a, b ∈ N
and
c ∈ Z
. Then there exists
u, v ∈ Z with c = ua + vb iff (a, b) | c.
Proof.
(
⇒
) Let
d
= (
a, b
). If
c
is a linear combination of
a
and
b
, then
d | c
because d | a and d | b.
(
⇐
) Suppose that
d | c
. Let
d
=
xa
+
yb
and
c
=
kd
. Then
c
= (
kx
)
a
+ (
ky
)
b
.
Thus c is a linear combination of a and b.
Note that the proof that (
a, b
) exists is existential, not constructive. How
can we actually find d, and how can we find x, y such that d = xa + yb?
While it might be easy to simply inspect
d
for small numbers, how would
you find common factors of, say, 4931 and 3795? We cannot use primes because
(a) prime factorization is hard; and (b) primes are not yet defined.
You might spot if
c |
4931 and
c |
3795, then
c |
(4931
−
3795) = 1136. The
process is also reversible — if
c |
1136 and
c |
3795, then
c |
(1136 + 3795) = 4931.
Thus the problem is equivalent to finding common factors of 3795 and 1136. The
process can be repeated until we have small numbers.
Proposition
(Euclid’s Algorithm)
.
If we continuously break down
a
and
b
by
the following procedure:
a = q
1
b + r
1
b = q
2
r
1
+ r
2
r
1
= q
3
r
2
+ r
3
.
.
.
r
n−2
= q
n
r
n−1
then the highest common factor is r
n−1
.
Proof.
We have (common factors of
a, b
) = (common factors of
b, r
1
) = (common
factors of r
1
, r
2
) = ··· = (factors of r
n−1
).
This gives an alternative proof that hcfs exist.
How efficient is this algorithm? For every step, we have
a ≥ b
+
r
1
>
2
r
1
.
Thus every two steps, the number on the left goes down by at least half. Hence
the number of digits goes down every 8 steps. Thus the time needed is
≤
8
×
number of digits and has time complexity O(log b).
Example. Suppose a = 57 and b = 42.
common factors of 57 and 42 57 = 1 × 42 + 15
= common factors of 42 and 15 42 = 2 × 15 + 12
= common factors of 15 and 12 15 = 1 × 12 + 3
= common factors of 12 and 3 12 = 4 × 3 + 0
= common factors of 3 and 0
= factors of 3.
So the hcf is 3.
By reversing Euclid’s Algorithm, we can find the hcf of two numbers as a
linear combination of a and b.
Example. Consider 57 and 21.
57 = 2 × 21 + 15
21 = 1 × 15 + 6
15 = 2 × 6 + 3
6 = 2 × 3
In the opposite direction, we have
3 = 15 − 2 × 6
= 15 − 2 × (21 − 15)
= 3 × 15 − 2 × 21
= 3 × (57 − 2 × 21) − 2 × 21
= 3 × 57 − 8 × 21
This gives an alternative constructive proof of B´ezout’s identity. Moreover,
it gives us a quick way of expressing (
a, b
) =
ax
+
by
. However, this algorithm
requires storing the whole process of Euclid’s Algorithm and is not efficient
space-wise.
To achieve higher space efficiency, we attempt to find a recurrence relation
for the coefficients
A
j
, B
j
such that
a × B
j
− b × A
j
= (
−
1)
j
r
j
. The possible
factor of
−
1 is there just so that the recurrence relation will look nicer. Suppose
that this is satisfied for all indices less than j. Then we have
(−1)
j
r
j
= (−1)
j
(r
j−2
− q
j
r
j−1
)
= (−1)
j−2
r
j−2
+ q
j
(−1)
j−1
r
j−1
= a(B
j−2
+ q
j
B
j−1
) − b(A
j−2
+ q
j
A
j−1
).
Hence we can obtain the following recurrence relation:
A
j
= q
j
A
j−1
+ A
j−2
B
j
= q
j
B
j−1
+ B
j−2
with
a × B
j
− b × A
j
= (−1)
j
r
j
.
In particular, a × B
n−1
− b × A
n−1
= (−1)
n−1
r
n−1
= (a, b).
Also, by an easy induction, A
j
B
j−1
− B
j
A
j−1
= (−1)
j
. So (A
j
, B
j
) = 1.
These coefficients also play another role. We can put the Euclid’s Algorithm’s
equations in the following form:
57
21
= 2 +
15
21
21
15
= 1 +
6
15
15
6
= 2 +
3
6
6
3
= 2
Then we can write out the fraction
57
21
in continued fraction form
57
21
= 2 +
1
1 +
1
2 +
1
2
Expanding this continued fractions term by term, we can have the sequence
2
,
2 +
1
1
= 3, 2 +
1
1+
1
2
=
8
3
. These are called the “convergents”. The sequence
happens to be
A
i
B
i
.