Part one - Florida Atlantic University



Chapter 1

Continued fractions and the Euclidean Algorithm

1.1 History of Continued Fractions

The following summary of the history of continued fractions was taken from Adam Van Tuyl [1] and John D. Barrow [2].

The origin of continued fractions is traditionally placed at the time of the creation of Euclid's Algorithm. Euclid's Algorithm is used to find the greatest common denominator (gcd) of two numbers. By algebraically manipulating the algorithm, one can derive the simple continued fraction of the rational p/q as opposed to the gcd of p and q. It is doubtful whether Euclid or his predecessors actually used this algorithm in such a manner. But due to its close relationship to continued fraction, the creation of Euclid's Algorithm signifies the initial development of continued fractions.

For more than a thousand years, any work that used continued fractions was restricted to specific examples. The Indian mathematician Aryabhata (d. 550 AD) used a continued fraction to solve a linear indeterminate equation. Rather than generalizing this method, his use of continued fractions is used solely in specific examples.

Throughout Greek and Arab mathematical writing, we can find examples and traces of continued fractions. But again, its use is limited to specific examples.

Two men from the city of Bologna, Italy, Rafael Bombelli (b. c.1530) and Pietro Cataldi (1548-1626) also contributed to this field, albeit providing more examples. Bombelli expressed the square root of 13 as a repeating continued fraction. Cataldi did the same for the square root of 18. Besides these examples, however, neither mathematician investigated the properties of continued fractions.

Continued fractions became a field in its right through the work of John Wallis (1616-1703). In his book Arithemetica Infinitorium (1655), he developed and presented the identity

[pic]

The first president of the Royal Society, Lord Brouncker (1620-1684) transformed this identity into

[pic]

Though Brouncker did not dwell on the continued fraction, Wallis took the initiative and began the first steps to generalizing continued fraction theory.

In his book Opera Mathematica (1695) Wallis laid some of the basic groundwork for continued fractions. He developed many of the properties of continued fractions that appear in this paper. It was also in this work that the term "continued fraction" was first used.

The Dutch mathematician and astronomer Christian Huygens (1629-1695) was the first to demonstrate a practical application of continued fractions. Huygens was building a mechanical model of the solar system and wanted to design the gear ratios to produce a proper scaled version of the planetary orbits. In Huygens’ day it was thought that the time required for the planet Saturn to orbit the Sun is 29.46 years (it is known to be 29.43 years). In order to model this motion correctly to scale, he needed to make two gears, one with P teeth, the other with Q teeth, so that P/Q is approximately 29.46. Since it tis hard to fashion small gears with a huge number of teeth, Huygens looked for relatively small values of P and Q. He calculated the continued fraction expansion of 29.46 and read off the first few rational approximations:[pic]. Thus, to simulate accurately Saturn’s motion with respect to that of the Earth’s, Huygens made one gear with 7 teeth and the other with 206 teeth.

[pic]

While the work of Wallis and Huygens began the work on continued fractions, the field of continued fractions began to flourish when Leonard Euler (1707-1783), Johan Heinrich Lambert (1728-1777), and Joseph Louis Lagrange (1736-1813) embraced the topic. Euler laid down much of the modern theory in his work De Fractionlous Continious (1737). He showed that every rational can be expressed as a terminating simple continued fraction. He also provided an expression for e in continued fraction form. He used this expression to show that e and e2 are irrational. He also demonstrated how to go from a series to a continued fraction representation of the series, and conversely.

Lambert generalized Euler's work on e to show that both ex and tan(x) are irrational if x is rational. Lagrange used continued fractions to find the value of irrational roots. He also proved that a real root of a solution to a quadratic equation is a periodic continued fraction.

The nineteenth century can probably be described as the golden age of continued fractions. As Claude Brezinski writes in History of Continued Fractions and Padre Approximations, "the nineteenth century can be said to be popular period for continued fractions." It was a time in which "the subject was known to every mathematician." As a result, there was an explosion of growth within this field.

Some of the more prominent mathematicians to make contributions to this field include Carl Jacobi (1904-1851), Oskar Perron (1880-1975), Charles Hermite (1822-1901), Carl Friedrich Gauss (1777-1855), Augustin-Louis Cauchy (1789-1857), and Thomas Jan Stieljes (1856-1894), sometimes called “the father of the analytic theory of continued fractions” for his work on the subject.

This brief sketch into the past of continued fractions is intended to provide an overview of the development of this field. Though its initial development seems to have to taken a long time, once started, the field and its analysis grew rapidly. The fact that continued fractions are still being used signifies that the field is still far from being exhausted. For example, in 1992, Rob Corless showed that the continued fraction algorithm gives rise to a chaotic dynamical system. Furthermore, Huygens' work on rational approximation is still used in modern computers.

1.2 Definition of continued fraction

A simple continued fraction is an expression in the form

[pic][pic]

Where all [pic] are integers.

A more convenient short notation for a continued fraction is [pic]. The first number represents the whole part of the fraction and it is separated from the fractional part by semicolon. The rest of the numbers in the list are written separated by commas.

For example, the continued fraction:

[pic]

Can be written also as [2; 1, 1, 3].

The numbers [pic] are called the quotients. The use of the word “quotient” will become clear when we look at the Euclidean Algorithm.

We will study patterns in the quotients and compare continued fraction expansions to expansions of numbers in some base b. We know that rational numbers, unlike irrational numbers, have expansions in any base b that are periodic or eventually periodic. We will see how this fact translates to their continued fractions.

Some similarities exist between the expansion of a number in base b and the continued fraction. For example, some numbers have a finite expansion in base b and others an infinite expansion. Continued fractions are finite and infinite as well. We will see if these definitions have the same meaning in both expansions.

Of course there are differences as well. For example, in the decimal expansion of a number only the digits from 0 to 9 can be used in each place value. In the continued fractions we will see that the quotients can be any integer.

1.3 Recursive Algorithm using the Decimal Expansion of a Number

Every real number x is represented by a point on the real number line, and falls between two successive integers, say n and n + 1:

n ( x < n + 1

In the case where x is an integer, then n = x.

The integer n is often called the floor of the real number x, and is written as:

n = (x(

The number u = x - n satisfies 0 ( u < 1. Thus, for a given real x there is a unique decomposition,

x = n + u

Where n is an integer and u satisfies 0 ( u < 1; u = 0 if and only if x is an integer. This decomposition is called the mod one decomposition of a real number [3].

This decomposition is the first step in the process of expanding x as a continued fraction, which is a recursive process.

Given x, we begin with the mod one decomposition:

x = n1 + u1 (3-1)

Where n1 is an integer and 0 ( u1 < 1.

If u1 = 0, then the recursive process terminates with this first step. If u1 > 0, then the reciprocal [pic] of u1 satisfies [pic] > 1 since u1 satisfies 0 < u1 < 1. In this case, the second step of the recursion is to apply the mod one decomposition to[pic], which yields:

[pic] (3-2)

Where n2 is an integer and u2 satisfies 0 ( u2 < 1. Combining (3-1) and (3-2), we get:

[pic] (3-3)

If [pic], the recursive process continues by writing the reciprocal of u2 that satisfies[pic]>1. We can now apply the decomposition to [pic]

[pic]

Where n3 is an integer and u3 satisfies 0 ( u3 < 1.

[pic]

The recursive process will end if u3 = 0. If u3 > 0, then the recursive process continues.

After k steps, we can write the real number as:

[pic]

Any real number can be expressed as a continued fraction using this recursive process. This process can easily be implemented in a spreadsheet calculation. Let’s see what we get for [pic]when we do that:

[pic] has a decimal expansion 1.414213562…. Using the recursive process, the continued fraction will be:

[pic]

Following this algorithm, it seems that the continued fraction for [pic], in short notation, would be: [pic].

We know that [pic] is an irrational number that does not have a periodic expansion in any base. However, looking at the continued fraction expansion, we can see periodicity. In part 2 we will see that indeed [pic]has periodicity in its continued fraction representation.

The recursive process to find the continued fraction is deeply attached to the Euclidean algorithm that will be defined in the next section.

1.4 The Euclidean Algorithm

The Euclidean Algorithm is used to find the greatest common divisor between two numbers. It is the solution to Proposition VII.2 in Euclid’s Elements:

“To find the greatest common measure of two given numbers not relatively prime”.

The algorithm is based on the following lemma with two observations:

Lemma 1:

1. If [pic]|[pic] then gcd ([pic],[pic]) =[pic].

No number ([pic], in particular) may have a divisor greater than the number itself.

2. If[pic], for integers [pic]and[pic], then gcd ([pic],[pic]) = gcd ([pic],[pic]).

Every common divisor of [pic] and [pic] also divides[pic]. Thus gcd ([pic],[pic]) divides[pic]. But gcd([pic],[pic]) also divides[pic]. Therefore, gcd ([pic],[pic]) is a common divisor of [pic] and [pic] so gcd ([pic],[pic])[pic]gcd ([pic],[pic]). The reverse is also true because every divisor of [pic] and [pic] also divides[pic].

The Euclidean Algorithm works as follows. Let’s assume that x0 > x1 and x1 does not divide x0.

[pic]

[pic]and [pic]are integers and with[pic].

A second division is done:

[pic]with [pic]

Continue this way, each time dividing the last remainder into the previous one, obtaining a new quotient and a new remainder. When we finally obtain a remainder that divides the previous remainder, the process is finished. The final nonzero remainder is the greatest common divisor of x0 and x1.

The Euclidean Algorithm can be summarized like this:

[pic]; [pic]

[pic]; [pic]

[pic]; [pic]

[pic]

[pic]

[pic]

In this case, [pic]is the last nonzero remainder and it is the gcd of x0 and x1.

For example, if we need to find gcd (1547, 560)

[pic]

Since 7(21, we are done. The greatest common divisor is the last non-zero remainder:

gcd(1547, 560) = 7

Following property 2 in lemma 1, we can see:

gcd(21, 28) = gcd(28, 133) = gcd(133, 427) = gcd(427, 560) = gcd(560, 1547) = 7

The Euclidean algorithm can be summarized in the following flowchart.

Given [pic] with [pic]

[pic]

1.5 The Euclidean Algorithm and Continued Fractions

The Euclidean Algorithm is equivalent to continued fractions. The Euclidean Algorithm is a recursive process defined as follow:

[pic]; [pic]

[pic]; [pic]

[pic]; [pic]

[pic]

[pic]

[pic]

Each of these equations can be rewritten like this:

[pic]divided by x1 ([pic] (5-1)

[pic]divided by x2 ([pic] (5-2)

[pic]divided by x3 ([pic] (5-3)

[pic]

[pic] divided by xk-1 ([pic] (5-4)

[pic]divided by xk ([pic] (5-5)

Equation (5-2) can be substituted in equation (5-1)

[pic] (5-6)

This process can be repeated, substituting equation (5-3) in equation (5-6)

[pic]

Continuing this process will give us a simple continued fraction.

[pic]

For example, in the previous section we found the gcd (1547, 560) using the Euclidean Algorithm:

[pic]

If we write the numbers 1547 and 560 as an improper fraction and find the continued fraction of that number, we get:

[pic]

Notice the numbers inside of the circles for both algorithms:

The quotients of the Euclidean Algorithm are the same as the terms of the continued fraction. This is the reason why the terms of the continued fraction are also called quotients.

The Euclidean Algorithm ends when we reach a remainder of 0. The Continued fraction ends when we get a 1 as the numerator of a fraction.

Conclusion:

• For integers [pic]and [pic]with [pic], the Euclidean algorithm for the gcd(m, n) is equivalent to the continued fraction of [pic].

• Since the Euclidean algorithm is always finite, it follows that the continued fraction for [pic] is also finite.

-----------------------

[pic]

[pic]

[pic]

[pic]

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download