An immediate corollary of this is that (Ai , Bi ) = 1.

Lemma 1.5.

a b

An = Bn = .

(a, b) (a, b)

a b a

Proof. (1.3) for i = n gives aBn = bAn . Therefore (a,b) Bn = (a,b) An . Now (a,b)

b

and (a,b) are coprime. An and Bn are coprime and thus this lemma is therefore an

immediate consequence of the following theorem.

Theorem 1.2. If d | ce and (c, d) = 1 then d | e.

Proof. Since (c, d) = 1 we can write 1 = cx + dy for some x, y ∈ Z. Then e =

ecx + edy and d | e.

De¬nition. The least common multiple (lcm) of a and b (written [a, b]) is the integer l

such that

1. a | l and b | l,

2. if a | l and b | l then l | l .

ab

It is easy to show that [a, b] = (a,b) .

1.4 Applications of the Euclidean algorithm

Take a, b and c ∈ Z. Suppose we want to ¬nd all the solutions x, y ∈ Z of ax + by = c.

A necessary condition for a solution to exist is that (a, b) | c, so assume this.

Lemma 1.6. If (a, b) | c then ax + by = c has solutions in Z.

Proof. Take x and y ∈ Z such that ax + by = (a, b). Then if c = q(a, b) then if

x0 = qx and y0 = qy , ax0 + by0 = c.

bk ak

Lemma 1.7. Any other solution is of the form x = x0 + y = y0 ’

(a,b) , for

(a,b)

k ∈ Z.

Proof. These certainly work as solutions. Now suppose x1 and y1 is also a solution.

a b a b

Then (a,b) (x0 ’ x1 ) = ’ (a,b) (y0 ’ y1 ). Since (a,b) and (a,b) are coprime we have

a b ak

(a,b) | (y0 ’ y1 ) and (a,b) | (x0 ’ x1 ). Say that y1 = y0 ’ (a,b) , k ∈ Z. Then

bk

x1 = x0 + (a,b) .

1.4. APPLICATIONS OF THE EUCLIDEAN ALGORITHM 5

1.4.1 Continued Fractions

We return to 525 and 231. Note that

535 63 1 1 1

=2+ = 2 + 231 = 2 + =2+ 1.

3 + 42

231 231 3 + 1+ 1

63 63 2

Notation.

535 1 11

=2+ = [2, 3, 1, 2] = 2; 3, 1, 2.

231 3+ 1+ 2

Note that 2, 3, 1 and 2 are just the qi ™s in the Euclidean algorithm. The rational

a

> 0 is written as a continued fraction

b

a 11 1

= q1 + ... ,

b q2 + q3 + qn

with all the qi ∈ N0 , qi ≥ 1 for 1 < i < n and qn ≥ 2.

a

with a and b ∈ N has exactly one expression in this

Lemma 1.8. Every rational b

form.

Proof. Existance follows immediately from the Euclidean algorithm. As for unique-

ness, suppose that

a 11 1

= p1 + ...

b p2 + p3 + pm

a 1

with the pi ™s as before. Firstly p1 = q1 as both are equal to < 1 then

. Since 1

b p2 + ...

a 1 a 1

’1 ’1

’ p1 = p2 + = ’ q1 = q2 + .

1 1

b b

p3 + q3 +

... ...

Thus p2 = q2 and so on.

Now, suppose that given [q1 , q2 , . . . , qn ] we wish to ¬nd a equal to it. Then we

b

A

work out the numbers Ai and Bi as in the Euclidean algorithm. Then a = Bn by b n

lemma (1.3).

A A

If we stop doing this after i steps we get Bi = [q1 , q2 , . . . , qi ]. The numbers Bi are

i i

called the “convergents” to a .

b

i

A (’1)

A

Using lemma (1.4), we get that Bi ’ Bi’1 = Bi’1 Bi . Now the Bi are strictly

i i’1

increasing, so the gaps are getting smaller and the signs alternate. We get

A1 A3 a A4 A2

< < ··· < < ··· < < .

B1 B3 b B4 B2

Ai a 1

’ ¤

The approximations are getting better and better; in fact Bi Bi+1 .

Bi b

— ” Continued fractions for irrationals

This can also be done for irrationals, but the continued fractions become in¬nite. For

instance we can get approximations to π using the calculator. Take the integral part,

print, subtract it, invert and repeat. We get π = [3, 7, 15, 1, . . . ]. The convergents are

3, 22 and 333 . We are already within 10’4 of π. There is a good approximation as Bi

√

7 106

increases. As an exercise, show that 2 = [1, 2, 2, 2, . . . ].

CHAPTER 1. INTEGERS

6

1.5 Complexity of Euclidean Algorithm

Given a and b, how many steps does it take to ¬nd (a, b). The Euclidean algorithm is

good.

Proposition. The Euclidean algorithm will ¬nd (a, b), a > b in fewer than 5d(b) steps,

where d(b) is the number of digits of b in base 10.

Proof. We look at the worst case scenario. What are the smallest numbers needing n

steps. In this case qi = 1 for 1 ¤ i < n and qn = 2. Using these qi ™s to calculate An

and Bn we ¬nd the Fibonacci numbers, that is the numbers such that F1 = F2 = 1,

Fi+2 = Fi+1 + Fi . We get An = Fn+2 and Bn = Fn+1 . So if b < Fn+1 then fewer

than n steps will do. If b has d digits then

√ 5d+2

1 1+ 5

d