The Euclidean Algortihm & Continued Fractions

Fig. 1- Solving continued fractions:


Fig 2: Another Set!

The Euclidean Algorithm and continued fractions (based on it) make fascinating mathematical fare and entertainment . First – what is the Euclidean algorithm::

A general theorem be stated thus:

If a is any integer, and b is any integer greater than zero, then we can always find an integer q such that:

a = b*q + r

where r is an integer satisfying the inequality:

0 < r < b

A general task is to find the “greatest common divisor” of a and b, called d(a,b). If d = (a,b)then positive or negative integers k and m can always be found such that:

d = ka + mb

and this proceeds by successive divisions with remainders.

As an example, consider the Euclidean algorithm for finding (a,b) = (61, 24). He gcd or greatest common divisor is 1 and we find:

61 = 2*24 + 13

24 = 1*13 + 11

13 = 1*11 + 2

11 = 5*2 + 1

2 = 2*1 + 0

From the 1st equation we have: 13 = 61 - 2*24

From the second:

11 = 24 – 13 = 24 - 61 - 2*24 = -61 + 3*24

From the third:

2 = 13 – 11 = (61 – 2*24) – (-61 + 3*24) = 2*61 – 5*24

From the fourth:

1 = 11 – 5*2 = (-61 + 3*24) – 5(2*61 – 5*24) = -11.61 + 28*24


Exercise: Carry out the Euclidean algorithm for finding the greatest common divisor of (187, 77)

Apart from these operations, we can also use the Euclidean algorithm to compute continued fractions. Examples are shown in Fig. 1 and Fig. 2.