# Periodic Continued Fractions

A periodic continued fraction is one which "repeats" --- for example,

In general, a periodic continued fraction has the form

If n is the length of the smallest repeating part, we say that the period is n. Thus, in the example above, the period is 2.

The primary result of this section is a theorem of Lagrange which charactertizes periodic continued fractions: They correspond to irrational numbers which are roots of quadratic equations with integer coefficients. Moreover, one part of the proof will require the construction of an algorithm for computing the continued fraction expansion for a quadratic irrational --- it is different from the general continued fraction algorithm, and important in its own right.

Before I begin, I should note that this section is rather long and technical. I've tried to write out the details with care to make them easy to follow, but they are often kind of dry. You've been warned!

Definition. A quadratic irrational is an irrational number which is a root of a quadratic equation

Proposition. A number is a quadratic irrational if and only if it can be written in the form , where , , and q is positive and not a perfect square.

Proof. Suppose x is a quadratic irrational. Then x is a root of

and and are integers, and , since .

If , then , which is a rational number, contrary to assumption.

If , then x is complex, again contrary to assumption.

Hence, .

Finally, if is a perfect square, then is rational. Hence, is not a perfect square.

For the converse, suppose , where , , and q is positive and not a perfect square. Then

This is a quadratic equation with integer coefficients, and since . Therefore, x is a quadratic irrational.

I'll prove the theorem of Lagrange in two parts. First, I'll show that periodic continued fractions represent quadratic irrationals.

I need a series of lemmas; the lemmas are motivated by the informal procedure of the following example.

Example. Write as a quadratic irrational.

I'll write x in closed form. Let . Then

On the other hand,

After some simplification, I get

y must be positive, so . Therefore,

The idea of the lemmas is simply to emulate the algebra I just did.

Lemma 1. If x is a quadratic irrational and is an integer, then is a quadratic irrational.

Proof. Write , where , , and b is positive and not a perfect square. Then

(I've suppressed the ugly algebra involved in combining the fractions and rationalizing the denominator.) The last expression is a quadratic irrational; note that , because b is not a perfect square.

Lemma 2. If x is a quadratic irrational and are integers, then the following expression is a quadratic irrational:

Proof. I'll use induction. The case was done in Lemma 1.

Suppose , and suppose the result is true for . nsider

By induction, the following subfraction is a quadratic irrational:

But the original fraction is just , so it's a quadratic irrational by Lemma 1. This completes the induction step, so the result is true for all .

Lemma 3. Let . Let

Then y can be written as , where .

Proof. Your experience with algebra should tell you this is obvious, but I'll give the proof by induction anyway.

For , I have

This has the right form.

Take , and assume the result is true for . Consider

By induction, for some ,

The original fraction is therefore

(I've suppressed some easy but ugly algebra again.) The last fraction is in the right form, so this completes the induction step. The result is therefore true for all .

I'm ready to prove that periodic continued fractions are quadratic irrationals. First, I'll consider those that start repeating immediately. These continued fractions are purely periodic, and I'll discuss them in more detail later.

Lemma 4. If , then is a quadratic irrational.

Proof. First, x is irrational, because it is an infinite continued fraction.

By Lemma 3, for some ,

Hence,

Therefore, x is a quadratic irrational.

In the general case, the fraction does not start repeating immediately.

Theorem. (Lagrange) Suppose , and let

Then x is a quadratic irrational.

Proof. is a quadratic irrational by Lemma 4. Therefore, is a quadratic irrational by Lemma 2.

The converse states the quadratic irrationals give rise to periodic continued fractions. Before I give the proof, here's an example which shows how you can go from a quadratic equation to a periodic continued fraction (at least in this case).

Suppose x is a quadratic irrational satisfying . This gives

Now substitute for x in the right side:

Do it again:

It's clear that you can keep going, and so .

The proof that quadratic irrationals give rise to periodic continued fractions will come out of an algorithm for computing the continued fraction for a quadratic irrational, which is useful in its own right. First, I need to be able to write a quadratic irrational in a "standard form".

Recall that a general quadatic irrational is an expression of the form , where , , , and b is not a perfect square. In the next lemma, I'll show that a quadratic irrational can be written in a special form, which I'll need for the algorithm which follows.

Lemma. Every quadratic irrational can be written in the form , where:

(a) .

(b) .

(c) .

(d) , and d is not a perfect square.

Proof. Let be a quadratic irrational, where , , , and b is not a perfect square. Write

First,

Thus, .

Obviously, .

Since , I have .

Since , I have . Since b is not a perfect square, is not a perfect square.

For example, is not in the form specified by the lemma. But I can write

Now which is divisible by 9, so the last fraction is in the correct form.

With a quadratic irrational expressed in this special form, I can construct an algorithm for computing its continued fraction. I'll compare this to the general continued fraction algorithm below.

Theorem. Let be a quadratic irrational, where , , , , and d is not a perfect square.

Then there are infinite sequences of integers , , and and an infinite sequence of irrational numbers defined by:

These sequences satisfy:

(a) and and for .

(b) .

Proof. Step 1. , , and are integers for . Further, and and for .

Clearly, is an integer for , and and are integers by definition. I also have .

Now

Since , it follows that . This means that is an integer, and I have . This shows that .

Thus, the assertions in this step are true for .

Suppose the assertions hold for k. Thus, and are integers and . Then is an integer.

If , then

This contradicts the assumption that d is not a square. Hence, .

Next,

This proves that , so is an integer.

From I get , so . This establishes the assertions in Step 1 by induction.

Step 2. .

Hence, . Since , this shows that the 's are the partial quotients of x.

Example. Use the quadratic irrational algorithm to compute the first 5 terms and convergents of the continued fraction for .

Note that , so the quadratic irrational is in the correct form.

The computation starts with , and

Then

Continuing in this way, I obtain:

It is interesting to compare this algorithm to the general continued fraction algorithm:

If I apply the general algorithm to , I get

I used a typical computer program to do the computation; you may get a slightly different result depending on what software you use. Notice that the partial quotients (which should be periodic) have started to be incorrect.

The general algorithm is unstable because the division magnifies the round-off errors which will occur in the floating-point computations. The quadratic irrational algorithm is more stable, and continues to produce the correct periodic partial quotients.

I will digress mometarily to prove an easy observation about the quadratic irrational algorithm. It's not needed for Lagrange's theorem, but I'll need it later in discussing continued fractions for irrationals of the form .

Proposition. Let be a quadratic irrational, where , , , , and d is not a perfect square. Suppose the quadratic irrational algorithm is applied to x, yielding sequences , , and .

Then if and only if .

Proof. If , then

Conversely, suppose . Then

Equating rational and irrational parts on the two sides, I have

Since , I have . Thus, .

As an example, here are the first 7 values of , , and for . Compare the values of and :

We continue with our discussion of Lagrange's theorem. Next, I need to derive some results on conjugates of quadratic irrationals.

Definition. Let , where . Let , and suppose d is not a perfect square. The conjugate of is

Note that if , then I get the number rational number , whose conjugate is itself.

The properties that follow are sufficiently formal that " " could be replaced with "x". Note that in all the expressions the "radical part" is the same ( ). I've switched from " " to " " for readability, since I need two quadratic irrationals for each property. The proof of this proposition is just tedious basic algebra, so you could skip it, or just work out some of the parts yourself.

Proposition. Let

Assume that , , , and u is not a perfect square.

(a) .

(b) .

(c) .

Proof. (a)

(b)

(c)

The fourth and fifth equalities used (b).

Now I can prove the other half of Lagrange's theorem.

Theorem. (Lagrange) The continued fraction for a quadratic irrational is periodic.

Proof. I will use the notation of the quadratic irrational continued fraction algorithm. Thus, I assume with , , , d is not a perfect square, and . Then the sequences , , , and are defined recursively by the algorithm.

The idea is to show that for large values of n, the 's and 's only assume only finitely many values. This will imply that the same is true for the 's, and hence that the continued fraction for x is periodic.

The first and longest step sets things up by showing that the 's are eventually positive.

Step 1. for sufficiently large n.

Recall that if x is an irrational number, the general continued fraction algorithm is

I showed that

The convergent of this continued fraction is equal to (since this is a finite continued fraction), and the convergents algorithm say that the convergent is . Thus,

In our situation, is a quadratic irrational . But the quadratic irrational continued fraction algorithm shows that is a quadratic irrational of the form --- that is, and are quadratic irrationals with the same radical term . Therefore, I may apply the properties of conjugates I derived:

Solve for :

As the convergents and both approach , and . It follows that

Moreover, for large n I have . So for large n,

Since , I have for large n.

Now using the notation of the quadratic irrational continued fraction algorithm,

So

Thus, for sufficiently large n,

Step 2. assumes only finitely many values For sufficiently large n.

For large n, I know is a positive integer, so . Hence,

For sufficiently large n I know is positive. Therefore, assumes only finitely many values (between 0 and d) for sufficiently large n.

Step 3. assumes only finitely many values For sufficiently large n.

For sufficiently large n I have . Hence,

Thus, . So assumes only finitely many values for sufficiently large n (and the same is true for ).

Step 4. The continued fraction for x is periodic.

Steps 3 and 4 show that for sufficiently large n the pairs assume only finitely many values. Therefore, there are distinct integers i and j --- say --- such that . Then

Thus,

Moreover, the quadratic irrational algorithm shows that if , then , and successive pairs continue to be equal. So

This proves that the continued fraction for x is periodic.

Contact information