Solutions to Euclidean Algorithm Problems

 1) Using the Euclidean Algorithm show the continued fraction for:  (237/ 139)

Solution:

(237/ 139)  = 1  · 139 + 98/139  = 1 +   1/ (139/ 98)

=>   (139/ 98) = 1 +  41 /98  =   1 +  1/ 98/41

 98/41  =   2 +  16/41 =  2 + 1 /41/16

=>  41/16 =  2 +  9/16 = 2+  1 / 16/9

16/9 =  1 + 7/9 =  1 +  1/9/7

9/7 = 1 + 2/7 =  1 + 1 /7/2

=>  7/2 = 3 + 1/2 =  3+  1/ 2/1

2/1 = 2

Then:  237/139 = 1.7

See graphic below:

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

Soln.

                                                                      Fig. 1

840/ 611 =   1  · 611 + 229/611 = 1 + 1/ 611/229

And:  611/229 =  2 + 153/229 =  2 + 1/ 229/153

=>   229/153 = 1 + 76/153 =  1 +  1/ 153/76

153/76 =  2 + 1/76

combining all of the preceding yields the result in Fig. 1 with C1= 840/611