# Continued Fractions and the Euclidean Algorithm

1 Introduction

Continued fractions offer a means of concrete representation for arbitrary real numbers . The
continued fraction expansion of a real number is an alternative to the representation of such a
number as a (possibly infinite) decimal .

The reasons for including this topic in the course on Classical Algebra are :

(i) The subject provides many applications of the method of recursion .
(ii) It is closely related to the Euclidean algorithm and, in particular, to “Bezout’s Identity”.
(iii) It provides an opportunity to introduce the subject of group theory via the 2-dimensional
unimodular group .

2 The continued fraction expansion of a real number

Every real number x is represented by a point on the real line and , as such, falls between two
integers. For example, if n is an integer and

n ≤ x < n + 1 ,

x falls between n and n + 1, and there is one and only one such integer n for any given real x.
In the case where x itself is an integer, one has n = x. The integer n is sometimes called the
floor of x, and one often introduces a notation for the floor of x such as

n = [x] .

Examples:

1. −2 = [−1.5]

2. 3 = [ ]

For any real x with n = [x] the number u = x − n falls in the unit interval I consisting of
all real numbers u for which 0 ≤ u < 1.

Thus, for given real x there is a unique decomposition

x = n + u

where n is an integer and u is in the unit interval. Moreover, u = 0 if and only if x is an
integer. This decomposition is sometimes called the mod one decomposition of a real number.
It is the first step in the process of expanding x as a continued fraction.

The process of finding the continued fraction expansion of a real number is a recursive process
that procedes one step at a time. Given x one begins with the mod one decomposition

where is an integer and .

If = 0, which happens if and only if x is an integer, the recursive process terminates with
this first step. The idea is to obtain a sequence of integers that give a precise determination
of x.

If > 0, then the reciprocal 1/ of satisfies 1/ > 1 since is in I and, therefore,
< 1. In this case the second step in the recursive determination of the continued fraction
expansion of x is to apply the mod one decomposition to 1/. One writes

where is an integer and 0 ≤ < 1. Combining the equations that represent the first two
steps, one may write

Either = 0, in which case the process ends with the expansion

or > 0. In the latter case one does to what had just been done to above under the
assumption > 0. One writes

where is an integer and 0 ≤ < 1. Then combining the equations that represent the first
three steps, one may write

After k steps, if the process has gone that far, one has integers and real numbers
that are members of the unit interval I with all positive. One
may write

Alternatively, one may write

If = 0, the process ends after k steps. Otherwise, the process continues at least one more
step
with

In this way one associates with any real number x a sequence, which could be either finite or
infinite, of integers. This sequence is called the continued fraction expansion of x.

Convention. When is called a continued fraction, it is understood that all of the
numbers are integers and that ≥1 for j ≥ 2.

3 First examples

Let

In this case one finds that

where

Further reflection shows that the continued fraction structure for y is self-similar:

This simplifies to

3y2 − 6y − 2 = 0

with discriminant 60. Since y > 2, one of the two roots of the quadratic equation cannot be
y, and, therefore,

Finally,

The idea of the calculation above leads to the conclusion that any continued fraction
that eventually repeats is the solution of a quadratic equation with positive discriminant and
integer coefficients. The converse of this statement is also true, but a proof requires further
consideration.

4 The case of a rational number

The process of finding the continued fraction expansion of a rational number is essentially
identical to the process of applying the Euclidean algorithm to the pair of integers given by its
numerator and denominator .

Let x = a/b, b > 0, be a representation of a rational number x as a quotient of integers a and
b. The mod one decomposition

shows that , where is the remainder for division of a by b. The case where
= 0 is the case where x is an integer. Otherwise > 0, and the mod one decomposition
of 1/ gives

This shows that , where is the remainder for division of b by . Thus, the
successive quotients in Euclid’s algorithm are the integers occurring in the continued
fraction. Euclid’s algorithm terminates after a finite number of steps with the appearance of a
zero remainder . Hence, the continued fraction expansion of every rational number is finite.

Theorem 1. The continued fraction expansion of a real number is finite if and only if the real
number is rational.

Proof. It has just been shown that if x is rational, then the continued fraction expansion of x is
finite because its calculation is given by application of the Euclidean algorithm to the numerator
and denominator of x . The converse statement is the statement that every finite continued
fraction represents a rational number. That statement will be demonstrated in the following
section.

 Prev Next

Start solving your Algebra Problems in next 5 minutes!

 Algebra Helper Download (and optional CD) Only \$39.99 Click to Buy Now: OR
2Checkout.com is an authorized reseller
of goods provided by Sofmath

Attention: We are currently running a special promotional offer for Algebra-Answer.com visitors -- if you order Algebra Helper by midnight of September 17th you will pay only \$39.99 instead of our regular price of \$74.99 -- this is \$35 in savings ! In order to take advantage of this offer, you need to order by clicking on one of the buttons on the left, not through our regular order page.

If you order now you will also receive 30 minute live session from tutor.com for a 1\$!

You Will Learn Algebra Better - Guaranteed!

Just take a look how incredibly simple Algebra Helper is:

Step 1 : Enter your homework problem in an easy WYSIWYG (What you see is what you get) algebra editor:

Step 2 : Let Algebra Helper solve it:

Step 3 : Ask for an explanation for the steps you don't understand:

Algebra Helper can solve problems in all the following areas:

• simplification of algebraic expressions (operations with polynomials (simplifying, degree, synthetic division...), exponential expressions, fractions and roots (radicals), absolute values)
• factoring and expanding expressions
• finding LCM and GCF
• (simplifying, rationalizing complex denominators...)
• solving linear, quadratic and many other equations and inequalities (including basic logarithmic and exponential equations)
• solving a system of two and three linear equations (including Cramer's rule)
• graphing curves (lines, parabolas, hyperbolas, circles, ellipses, equation and inequality solutions)
• graphing general functions
• operations with functions (composition, inverse, range, domain...)
• simplifying logarithms
• basic geometry and trigonometry (similarity, calculating trig functions, right triangle...)
• arithmetic and other pre-algebra topics (ratios, proportions, measurements...)

ORDER NOW!

 Algebra Helper Download (and optional CD) Only \$39.99 Click to Buy Now: OR
2Checkout.com is an authorized reseller
of goods provided by Sofmath

 "It really helped me with my homework.  I was stuck on some problems and your software walked me step by step through the process..." C. Sievert, KY

 Sofmath 19179 Blanco #105-234San Antonio, TX 78258 Phone: (512) 788-5675Fax: (512) 519-1805
 Home   : :   Features   : :   Demo   : :   FAQ   : :   Order Copyright © 2004-2021, Algebra-Answer.Com.  All rights reserved.