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
By the quadratic formula,
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 quadratic irrational algorithm gives
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.
The quadratic irrational algorithm gives
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.
Copyright 2024 by Bruce Ikenaga