periodic continued fractions represent quadratic irrationals
This article shows that infinite simple continued fractions^{} that are eventually periodic correspond precisely to quadratic irrationals.
Throughout, we will freely use results on convergents^{} to a continued fraction; see that article for details.
Definition 1.
A periodic simple continued fraction is a simple continued fraction
$$[{a}_{0},{a}_{1},{a}_{2},\mathrm{\dots}]$$ |
such that for some $k\ge 0$ there is $m>0$ such that whenever $r\ge k$, we have ${a}_{r}={a}_{r+m}$. Informally, a periodic continued fraction^{} is one that eventually repeats. A purely periodic simple continued fraction is one for which $k=0$; that is, one whose repeating period starts with the initial element.
If
$$[{a}_{0},{a}_{1},\mathrm{\dots},{a}_{k-1},{a}_{k},\mathrm{\dots},{a}_{k+j-1},{a}_{k},\mathrm{\dots},{a}_{k+j-1},{a}_{k},\mathrm{\dots}]$$ |
is a periodic continued fraction, we write it as
$$[{a}_{0},{a}_{1},\mathrm{\dots},{a}_{k-1},\overline{{a}_{k},\mathrm{\dots},{a}_{k+j-1}}].$$ |
Theorem 1.
If
$$\alpha =[{a}_{0},{a}_{1},\mathrm{\dots},{a}_{r},\overline{{b}_{1},\mathrm{\dots},{b}_{t}}]$$ |
is a periodic simple continued fraction, then $\alpha $ is a quadratic irrational $p\mathrm{+}q\mathit{}\sqrt{d}$ for $p\mathrm{,}q$ rational and $d$ squarefree^{}. Conversely, every such quadratic irrational is represented by such a continued fraction.
Proof.
The forward direction is pretty straightforward. Given such a continued fraction, let $\beta $ be the ${(r+1)}^{\mathrm{st}}$ complete convergent, i.e.
$$\beta =[\overline{{b}_{1},\mathrm{\dots},{b}_{t}}]$$ |
Note first that $\beta $ must be irrational since the continued fraction for any rational number terminates. Then the article on convergents to a continued fraction shows that
$$\beta =\frac{\beta {p}_{t}+{p}_{t-1}}{\beta {q}_{t}+{q}_{t-1}}$$ |
where the ${p}_{i},{q}_{i}$ are the convergents to the continued fraction for $\beta $. Thus
$${q}_{t}{\beta}^{2}+({q}_{t-1}-{p}_{t})\beta -{p}_{t-1}=0$$ |
and thus $\beta $ is irrational and satisfies a quadratic equation so is a quadratic irrational. A simple computation then shows that $\alpha $ is as well.
In the other direction, suppose that $\alpha $ is a quadratic irrational satisfying
$$a{\alpha}^{2}+b\alpha +c=0$$ |
and with continued fraction representation^{}
$$\alpha =[{a}_{0},{a}_{1},\mathrm{\dots}]$$ |
Then for any $n>0$, we have
$$\alpha =\frac{{t}_{n}{p}_{n-1}+{p}_{n-2}}{{t}_{n}{q}_{n-1}+{q}_{n-2}}$$ |
where the ${t}_{i}$ are the complete convergents of the continued fraction, so that from the quadratic equation we have
$${A}_{n}{t}_{n}^{2}+{B}_{n}{t}_{n}+{C}_{n}=0$$ |
where
$${A}_{n}=a{p}_{n-1}^{2}+b{p}_{n-1}{q}_{n-1}+c{q}_{n-1}^{2}$$ | ||
$${B}_{n}=2a{p}_{n-1}{p}_{n-2}+b({p}_{n-1}{q}_{n-2}+{p}_{n-2}{q}_{n-1})+2c{q}_{n-1}{q}_{n-2}$$ | ||
$${C}_{n}=a{p}_{n-2}^{2}+b{p}_{n-2}{q}_{n-2}+c{q}_{n-2}^{2}={A}_{n-1}$$ |
Note that ${A}_{n}\ne 0$ for each $n>0$ since otherwise
$$a{p}_{n-1}^{2}+b{p}_{n-1}{q}_{n-1}+c{q}_{n-1}^{2}=0$$ |
so that
$$a{\left(\frac{{p}_{n-1}}{{q}_{n-1}}\right)}^{2}+b\frac{{p}_{n-1}}{{q}_{n-1}}+c=0$$ |
and the quadratic equation would have a rational root, contradicting the fact that $\alpha $ is irrational.
The remainder of the proof is an elaborate computation that shows we can bound each of ${A}_{n},{B}_{n},{C}_{n}$ independent of $n$. Assuming that, it follows that there are only a finite number of possibilities for the triples $({A}_{n},{B}_{n},{C}_{n})$, so we can choose ${n}_{1},{n}_{2},{n}_{3}$ such that
$$({A}_{{n}_{1}},{B}_{{n}_{1}},{C}_{{n}_{1}})=({A}_{{n}_{2}},{B}_{{n}_{2}},{C}_{{n}_{2}})=({A}_{{n}_{3}},{B}_{{n}_{3}},{C}_{{n}_{3}})$$ |
Then each of ${t}_{{n}_{1}},{t}_{{n}_{2}},{t}_{{n}_{3}}$ is a root of (say)
$${A}_{{n}_{1}}{t}^{2}+{B}_{{n}_{1}}t+{C}_{{n}_{1}}$$ |
so that two of them must be equal. But then ${t}_{{n}_{1}}={t}_{{n}_{2}}$ (say), and
$${t}_{{n}_{1}}=[{a}_{{n}_{1}},{a}_{{n}_{1}+1},\mathrm{\dots}]$$ | ||
$${t}_{{n}_{2}}=[{a}_{{n}_{2}},{a}_{{n}_{2}+1},\mathrm{\dots}]$$ |
and the continued fraction is periodic.
We proceed to find the bounds. We know that
$$ |
so that
$$\alpha -\frac{{p}_{n-1}}{{q}_{n-1}}=\frac{\u03f5}{{q}_{n-1}^{2}}$$ |
for some $\u03f5$ (depending on $n$) with $$. Thus
${A}_{n}$ | $=a{p}_{n-1}^{2}+b{p}_{n-1}{q}_{n-1}+c{q}_{n-1}^{2}$ | ||
$=a{\left(\alpha {q}_{n-1}+{\displaystyle \frac{\u03f5}{{q}_{n-1}}}\right)}^{2}+b{q}_{n-1}\left(\alpha {q}_{n-1}+{\displaystyle \frac{\u03f5}{{q}_{n-1}}}\right)+c{q}_{n-1}^{2}$ | |||
$=(a{\alpha}^{2}+b\alpha +c){q}_{n-1}^{2}+2a\alpha \u03f5+a{\displaystyle \frac{{\u03f5}^{2}}{{q}_{n-1}^{2}}}+b\u03f5$ | |||
$=2a\alpha \u03f5+a{\displaystyle \frac{{\u03f5}^{2}}{{q}_{n-1}^{2}}}+b\u03f5$ |
so that
$$ |
and thus also
$$ |
It remains to bound ${B}_{n}$. But
$${B}_{n}^{2}-4{A}_{n}{C}_{n}={(2{A}_{n}{t}_{n}+{B}_{n})}^{2}$$ |
Substituting the values of ${A}_{n},{B}_{n}$ on the right, and using the fact that
$${t}_{n}=-\frac{{p}_{n-2}-x{q}_{n-2}}{{p}_{n-1}-x{q}_{n-1}}$$ |
we get after a computation
$\sqrt{{B}_{n}^{2}-4{A}_{n}{C}_{n}}$ | $=({p}_{n-1}{q}_{n-2}-{p}_{n-2}{q}_{n-1}){\displaystyle \frac{2ax{p}_{n-1}+b{p}_{n-1}+bx{q}_{n-1}+2c{q}_{n-1}}{{p}_{n-1}-x{q}_{n-1}}}$ | ||
$=\pm {\displaystyle \frac{(2ax+b){p}_{n-1}+(2a{x}^{2}+2bx+2c){q}_{n-1}-(2a{x}^{2}+bx){q}_{n-1}}{{p}_{n-1}-x{q}_{n-1}}}$ | |||
$=\pm {\displaystyle \frac{({p}_{n-1}-x{q}_{n-1})(2ax+b)}{{p}_{n-1}-x{q}_{n-1}}}=\pm (2ax+b)$ |
so that
$${B}_{n}^{2}-4{A}_{n}{C}_{n}={(2ax+b)}^{2}={b}^{2}-4ac$$ |
Thus
$$ |
and we have thus bounded all of ${A}_{n},{B}_{n},{C}_{n}$ independent of $n$. ∎
References
- 1 G.H. Hardy & E.M. Wright, An Introduction to the Theory of Numbers, Fifth Edition, Oxford Science Publications, 1979.
Title | periodic continued fractions represent quadratic irrationals |
---|---|
Canonical name | PeriodicContinuedFractionsRepresentQuadraticIrrationals |
Date of creation | 2013-03-22 18:04:40 |
Last modified on | 2013-03-22 18:04:40 |
Owner | rm50 (10146) |
Last modified by | rm50 (10146) |
Numerical id | 9 |
Author | rm50 (10146) |
Entry type | Theorem |
Classification | msc 11Y65 |
Classification | msc 11A55 |
Defines | periodic continued fraction |
Defines | purely periodic |