WOLFRAM|DEMONSTRATIONS PROJECT

The Euclidean Algorithm and Simple Continued Fractions

​
a, b
987
=
610
×
1
+
377
610
=
377
×
1
+
233
377
=
233
×
1
+
144
233
=
144
×
1
+
89
144
=
89
×
1
+
55
89
=
55
×
1
+
34
55
=
34
×
1
+
21
34
=
21
×
1
+
13
21
=
13
×
1
+
8
13
=
8
×
1
+
5
8
=
5
×
1
+
3
5
=
3
×
1
+
2
3
=
2
×
1
+
1
2
=
1
×
2
+
0
987
——
610
=
1
+
1
1
+
1
1
+
1
1
+
1
1
+
1
1
+
1
1
+
1
1
+
1
1
+
1
1
+
1
1
+
1
1
+
1
1
+
1
2
This Demonstration shows the connection between the continued fraction expansion of a rational number
a/b
and the Euclidean algorithm applied to the pair of integers
a
and
b
.