Suppose that the continued fraction of some irrational \(x\) is repeating, i.e \(x \twoheadrightarrow x\). Then we can write \(x = [a_0,\dots ,a_n ,x]\). We can
simplify the right hand side to a quotient of two linear polynomials in \(x\), showing that \(x\) is the root of a quadratic equation. More precisely if \(\frac {d_i}{e_i}\), by the magic box, \(x = \frac
{d_nx+d_{n-1}}{e_{n}x+e_{n-1}}\), so \(x = \frac {-(e_{n-1}-d_n)\pm \sqrt {(e_{n-1}-d_n)^2+4e_nd_{n-1}}}{2e_n}\). Using the determinant identity from the magic box, this is equal to \(x = \frac
{-(e_{n-1}-d_n)\pm \sqrt {(e_{n-1}+d_n)^2+4(-1)^n}}{2e_n}\). Replace \(n\) with \(kn\), and let \(k \to \infty \) and noting that \(e_n \to \infty \), the two roots are \(\lim _{k\to \infty }-\frac
{e_{kn-1}}{e_{kn}}\) for negative, and \(\lim _{k\to \infty }\frac {d_{kn}}{e_{kn}}\) for positive. But the first is \(y| \frac {-1}y = [a_n,\dots ,a_0,y]\), and the latter is \(x\), so we get:
Theorem3.1. If \(x\) has continued fraction \([a_0,\dots a_n,x]\), then
\(x = \frac {-(e_{n-1}-d_n)+\sqrt {(e_{n-1}+d_n)^2+4(-1)^n}}{2e_n}\) where \(\frac {d_n}{e_n}\) is the \(n^{th}\) convergent. Moreover, \(a_i,d_i,e_i>0\), \(x>1\),\(-1<\bar {x}<0\), and
\(\frac {-1}{\bar {x}} = [a_n,\dots , a_0,\frac {-1}{\bar {x}}]\).
Even if \(x\) has a continued fraction that eventually repeats, ie. \(x \twoheadrightarrow y \twoheadrightarrow y\), we can subtract the first few terms and take reciprocals to get another number with repeating continued
fraction, so \(x\) will lie in the field generated by that element, hence will again be the root of some quadratic polynomial.
In the case that \(x = \sqrt {d}\), there is a fast way to organize the computation of the continued fraction of \(x\). Normally, at each step, we would expect to have something of the form \(\frac {a + g\sqrt {d}}{b}\),
subtract its floor, and compute its reciprocal in \(\QQ [\sqrt {d}]\). However in this case, at every step, \(g=1\)! To see this, let \(c\) be the floor of \(\frac {a+\sqrt {d}}{b}\). Then at the next step we will have \(\frac
{b(bc-a+\sqrt {d})}{-\N (a-bc+\sqrt {d})}\). So in the next step \(g = 1\) iff \(b|\N (a-bc+\sqrt {d})\) iff \(a^2\equiv d \pmod b\). If this is the case, then letting \(x = bc-a\), \(y = \frac {d-x^2}{b}\), we get
that the number at the next step is \(\frac {x+\sqrt {d}}{y}\). Note that \(x^2\equiv d \pmod y\) by definition of \(y\). Thus if \(g = 1\) at one step and \(a^2 \equiv d \pmod b\), then \(g=1\) at every step. Moreover,
we have seen how to compute the next step, and we can organize this information into a table called the super magic box.
We will consider the super magic box for \(\frac {a_0+\sqrt {n}}{b_0}\), where \(a_0^2 \equiv n \pmod {b_0}\). Note that the congruence condition can always be arranged by multiplying the denominator and numerator
by a sufficiently divisible number (for example \(b_0\)). Let \(w = \floor {\sqrt {n}}\). Then we write a table
Then \(\frac {a_i+\sqrt {n}}{b_i} = [c_i,c_{i+1},\dots ]\), so in particular the \(c_i\) are convergents of the original number.
We can bound \(b_{i+1}\) in terms of \(b_{i}\) and \(n\). Note that WLOG we can assume \(c_i = 0\) by subtracting it off. Now, assume that \(b_i>0\). Thus \(b_{i+1} = \frac {n-a_i^2}{b_i}\). Clearly \(b_{i+1}
\leq \frac {n}{b_i}\). Now note that \(b_i-\sqrt {n} \geq a_i \geq -\sqrt {n}\). This shows that either \(|b_{i+1}|<|b_i|-2\sqrt {n}\) or \(|b_{i+1}|\) is less than \(\max \{n,2\sqrt {n}\}\). If
\(b_i<0\), \(\sqrt {n}-b_i \geq -a_i \geq \sqrt {n}\). It follows that \(0 \leq b_{i+1} \leq -b_i+2\sqrt {n}\). Thus it follows that \(|b_i| \leq 2\sqrt {n}+\max \{|b_0|,n\}\) so that there are only finitely
many values it takes on. The bounds for \(a_i\) above in general give bounds on \(a_{i+1}\) dependant on \(b_{i}\), so there are also finitely many possibilities for the \(a_i\). Thus the columns of the super magic box repeat
and we get:
Theorem3.2. \(a\) has an eventually repeating continued fraction iff \(a\) lies
in a real quadratic field. When it repeats, \(c_i,b_i,a_i>0\), \(2a_i,b_i<2\sqrt {n}\).
Proof. \(c_i\) is clearly positive, \(b_i\) is positive by the theorem on irrationals with repeating continued fractions, and \(a_i\) is positive since \(\frac {{a_i}-\sqrt {n}}{b_i}
\in (-1,0)\), and \(\frac {a_i+\sqrt {n}}{b_i}>1\) which implies the bound. The average of the number and its conjugate is \(\frac {a_i}{b_i}\), which cannot be negative, so \(a_i>0\). \(a_i < \sqrt {n}\)
follows from the fact that \(\frac {a_i-\sqrt {n}}{b_i}\) is negative. □
When does a number \(r\) have strictly repeating continued fraction? A necessary condition is that \(r>1\) and \(\bar {r} \in (-1,0)\). Is this sufficient? Say that \(r\) is regular if it is in some real quadratic
field and satisfies these two conditions. We can try to run the magic box backwards.
Lemma3.3. If \(r\) is regular, then there is a unique regular \(r_{-1}\) with \(r_{-1} \to r\).
Proof. \(0<\frac {1}{r}<1\) and \(\frac {1}{\bar {r}}<-1\). Thus there is a unique number such \(n>0\) such that \(\frac {1}{\bar {r}}+n \in (-1,0)\). Let
\(r_{-1} = \frac {1}{r}+n\). □
Thus we can run a reverse super magic box on \(r\). One has to check via a calculation that this works with some constant number in the square root. By the bounds for Theorem 3.2, \(a_i,b_i\) take on finitely many values. Thus it eventually repeats. But going forward, this means that \(r\) has a repeating continued
fraction! We obtain:
Theorem3.4. \(r\) is regular iff \(r\) has a repeating continued fraction.
As an application, we can study the continued fraction of \(\sqrt {r}\) where \(r\) is a positive rational.
Theorem3.5. If \(r>1\) is a rational, then \(\sqrt {r}\) has a continued fraction of the form
\([a_0,\overline {a_1,\dots a_{r}}]\), where the line signifies repetition. Moreover, \(a_r = 2a_0\), and \(a_i = a_{r-i+1}\).
Proof. To see that the continued fraction is of that form, we only need to note that \(\sqrt {r}+\floor {\sqrt {r}}\). satisfies the conditions of the theorem above. To see the last
two conditions, note that \(\frac {-1}{\bar {\sqrt {r}}} = \frac {1}{\sqrt {r}}\) so that \(\sqrt {r} = [a_0,\overline {a_1,\dots a_{r}}] = [a_0,\overline {a_1,\dots a_{r}}] = [a_0,\overline
{a_1,\dots a_{r}-a_0,0,a_0}] = [\overline {a_0,a_1,\dots a_{r}-a_0,0}]\) but on the other hand it is equal to \([0,\overline {0,a_r-a_0, a_{r-1}\dots a_{0}}] = [\overline {a_r-a_0, a_{r-1}\dots
a_{0},0}] = [a_r-a_0, \overline {a_{r-1}\dots a_{0},0,a_r-a_0}] = [a_r-a_0, \overline {a_{r-1}\dots a_{1},a_r}]\) by the last part of Theorem 3.1. □
Given a non-square \(d\), we can find all solutions \((x,y)\) to Pell’s equation,\(x^2-dy^2=\pm 1\) using continued fractions. This is the same as finding a \(x+\sqrt {d}y\) with norm \(\pm 1\). WLOG, we can assume
\(x,y>0\), which is the same as restricting to \(x+\sqrt {d}y > 1\).
Theorem3.6. If \(x,y>0\), and \((x,y)\) solves Pell’s equation, \(\frac {x}{y}\) is a convergent
of \(\sqrt {d}\). Infinitely many such solutions exist, and are powers of a fundamental solution.
Proof. \(|x^2-dy^2|=1 \implies |\frac {x}{y}-\sqrt {d}|\leq \frac {1}{y^2|\frac {x}{y}+\sqrt {d}|} \leq \frac {1}{2y^2}\), so \(x,y\) is a solution. To see that a
solution exists, note that \(|b_k^2-dc_k^2|\) is bounded above by a constant like \(2d+1\). These infinitely many things must generate finitely many ideals, since there are finitely many index \(n\) subgroups of \(\ZZ ^2\). Thus
there are infinitely many units. Taking log of the positive units, they must form a discrete subgroup as the convergents are discrete. Thus there is a fundamental solution. □