The Euclidean Algorithm and the Path to Continued Fractions

The Euclidean Algorithm is actually the means to obtain continued fractions.  What is the Euclidean algorithm? A general theorem can 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.

Consider using the Euclidean algorithm for finding:

 (a,b) = (61, 24). 

Here gcd or the greatest common divisor is 1 and we find, repeating the same process over until an equality emerges:

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

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

Solution:

To use the Euclidean algorithm on (187,77)

Take (a,b) = (187, 77)  = 2 R33 [e.g. 187 – 154]

= 2*77 + 33   or  just (77, 33)

So take:

(77)/ 33 = 2 R11 [e.g. 77 – 66 = 11]

= 2*33 + 11 = (33, 11) = 3*11 + 0

Hence: (187, 77) = (33,11)


Another example problem:

Reduce (245, 193) via the Euclidean Algorithm:

(a,b) = (245, 193)

=> (245) / 193 = 1 R52 [e.g. 245 – 193 = 52]

= 1*193 + 52 = (193, 52)

ð (193)/ 52 = 3 R 37 [e.g. 193 – 156 = 33]

= 3*52 + 37 = (52, 37)

But: (52, 37) = (52)/ 37 = 1 R 15 [e.g. 52 – 37 = 15]

= 1*37 + 15 = (37, 15)

But (37, 15) => (37)/ 15 = 2 R 1 = 2*7 + 1

= (7, 1)

7/1 = 7 Hence

(245, 193) = (193, 52) = (52, 37) = (37, 15) = (15, 7) = (7, 1)


Now, let’s look more closely at continued fractions:

                            Fig. 1 - Continued fractions

We see in the graphic above how 2/5 is converted into a continued fraction. Next consider 169/70 and seek the continued fraction development:

We have:

169/70 = 2 + 29/70 = 2 + 1/70/29

70/29 = 2 + 12/29 = 2 + 1/ (29/12)

29/12 = 2 + 5/18 = 2 + 1/ (12/5)

12/5 = 2 + 2/5 = 2 + 1/(5/2)

And: 5/2 = 2 ½ = 2 + ½

Thus 169/70 is finally developed as shown below with result = 2.414

The key flag that the process is at an end is the final fraction is proper and also simple. No further processing is needed and the continued fraction form is now complete. 

Suggested Problem: 

1) Using the Euclidean Algorithm show the continued fraction for:

(237/ 139)

2) Show how the continued fraction for 840/ 611 results in C1 = 1.375  (Refer to top of Fig. 1)