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

.