More on the Euclidean Algorithm and Continued Fractions

The continued fraction development for (169/ 70) - See text!

We left off the last installment with the exercise:

To use the Euclidean algorithm on (187,77)

We have (a,b) = (187, 77)

Take:


(187)/ 77 = 2 R33 [e.g. 187 – 154]

= 2*77 + 33

ð (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 problem:

Reduce (245, 193) via the Euclidean Algortihm:

(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:

We saw in Fig, 1 from the previous blog how 2/5 was converted into a continued fraction.

Now we look at 169/70 and seek the continued fraction development:

Then:

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 developed as shown (Fig. 1) with result = 2.414

Problem: Using the Euclidean Algorithm show the continued fraction for:

(237/ 139)

Show the full continued fraction.