This course develops continued fractions as a bridge between the Euclidean algorithm, rational approximation, quadratic irrationals, and Pell equations. The guiding question is simple: when a real number is approximated by rationals, why do certain denominators give much better answers than their size would suggest? The chapters build the answer in stages. We first turn repeated division into finite continued fractions for rational numbers, then pass to infinite continued fractions for irrational numbers and prove that their convergents really recover the original number. The next chapters study why those convergents are arithmetically special: they give sharp error bounds, best-approximation properties, and the standard elementary route to Dirichlet and Hurwitz type estimates. The second half of the course focuses on structure and computation. Periodic continued fractions characterize quadratic irrationals, square roots have especially concrete period algorithms, and the period of $\sqrt{D}$ controls the Pell equations $x^2-Dy^2=1$ and $x^2-Dy^2=-1$. The final chapters collect exact computational certificates and a short optional synthesis through interval maps and matrix products. [remark: Recurring Computations] Nearly every calculation in the course returns to three formulas: the recurrence for convergents, the determinant identity for adjacent convergents, and the error estimate involving consecutive denominators. Keeping these formulas visible makes the later theory computational rather than mysterious. [/remark] # 1. Euclidean Algorithm and Finite Continued Fractions This opening chapter explains how continued fractions arise from the Euclidean algorithm. The only prerequisites are integer division with remainder, greatest common divisors, and basic manipulation of rational numbers. The guiding question is: when a rational number is divided repeatedly into integer and fractional parts, what information is preserved, and how can it be recovered? The answer is a finite list of positive integers after the first term, and this list gives both an exact expression for the rational number and a sequence of rational approximations called convergents. ## From Division to Continued Fractions The first problem is to encode repeated division without losing the quotients produced by the Euclidean algorithm. If $x>0$ is rational, write $x=a_0+r_0$ with $a_0\in\mathbb Z$ and $0\le r_0<1$. When $r_0\ne 0$, the reciprocal $1/r_0$ is again positive rational, so the same division step may be repeated. [definition: Finite Simple Continued Fraction] Let $a_0\in\mathbb Z$ and let $a_1,\dots,a_n\in\mathbb N$. The finite simple continued fraction with partial quotients $a_0,a_1,\dots,a_n$ is the rational number \begin{align*} [a_0;a_1,\dots,a_n]=a_0+\frac{1}{a_1+\frac{1}{a_2+\cdots+\frac{1}{a_n}}}. \end{align*} [/definition] The semicolon separates the integer part $a_0$ from the positive partial quotients that follow it. For positive rational numbers greater than $1$, $a_0$ is the first quotient in the Euclidean algorithm; for numbers in $(0,1)$, $a_0=0$ and the remaining data begins after taking a reciprocal. [example: Euclidean Expansion of 415 Over 93] Consider the rational number \begin{align*} \frac{415}{93}. \end{align*} Applying division with remainder gives \begin{align*} 415=4\cdot 93+43. \end{align*} The next divisions are \begin{align*} 93=2\cdot 43+7, \end{align*} \begin{align*} 43=6\cdot 7+1, \end{align*} and finally \begin{align*} 7=7\cdot 1+0. \end{align*} Dividing the first equality by $93$ gives \begin{align*} \frac{415}{93}=4+\frac{43}{93}. \end{align*} From $93=2\cdot 43+7$, division by $43$ gives \begin{align*} \frac{93}{43}=2+\frac{7}{43}. \end{align*} Taking reciprocals of both positive sides therefore gives \begin{align*} \frac{43}{93}=\frac{1}{2+\frac{7}{43}}. \end{align*} From $43=6\cdot 7+1$, division by $7$ gives \begin{align*} \frac{43}{7}=6+\frac{1}{7}. \end{align*} Taking reciprocals again gives \begin{align*} \frac{7}{43}=\frac{1}{6+\frac{1}{7}}. \end{align*} Substituting this into the previous reciprocal expression gives \begin{align*} \frac{43}{93}=\frac{1}{2+\frac{1}{6+\frac{1}{7}}}. \end{align*} Substituting this value of $43/93$ into the first decomposition yields \begin{align*} \frac{415}{93}=4+\frac{1}{2+\frac{1}{6+\frac{1}{7}}}. \end{align*} Thus, by the definition of a finite simple continued fraction, \begin{align*} \frac{415}{93}=[4;2,6,7]. \end{align*} The partial quotients $4,2,6,7$ are exactly the nonzero quotients produced by the Euclidean algorithm, recorded in the same order. [/example] The example gives a construction, but a representation theory also needs to answer whether the construction always stops and whether two different lists can name the same rational number. There is a genuine final-step ambiguity: when $a_n>1$, \begin{align*} [a_0;\dots,a_n]=[a_0;\dots,a_n-1,1]. \end{align*} The next theorem states that this is the only ambiguity and fixes it by requiring the last partial quotient to be greater than $1$. [quotetheorem:5500] [citeproof:5500] The uniqueness theorem tells us that the Euclidean algorithm is not merely a way of finding an expansion; after the final-term convention is imposed, it is the expansion. The hypotheses matter: positivity keeps the Euclidean process in the form used here, while rationality is what makes the chain of remainders terminate; irrational numbers require infinite continued fractions instead. If later partial quotients were allowed to be negative, even a positive rational would lose the standard convention: for instance \begin{align*} [1;2]=[2;-2]=\frac{3}{2}, \end{align*} so the same number would be encoded by incompatible quotient lists. The convention $a_n>1$ is also necessary for uniqueness, since \begin{align*} [2;3]=[2;2,1], \end{align*} so allowing a terminal $1$ creates two finite simple continued fraction expansions for the same rational number. The theorem does not say that finite continued fractions approximate irrationals, nor does it yet give an efficient way to compute the intermediate truncations. To use this representation effectively, we now need to compute its successive truncations without repeatedly simplifying a nested fraction from scratch. ## Convergents and Recurrence Relations The next problem is computational. The expression $[a_0;a_1,\dots,a_n]$ contains nested fractions, and direct simplification becomes awkward for long expansions. The useful replacement is a pair of integer recurrences that produce the numerator and denominator of each truncation. [definition: Convergent] Let $[a_0;a_1,\dots,a_n]$ be a finite simple continued fraction. For $0\le k\le n$, the $k$th convergent is \begin{align*} \frac{p_k}{q_k}=[a_0;a_1,\dots,a_k], \end{align*} where $p_k,q_k\in\mathbb Z$ and $q_k>0$. [/definition] Convergents are the rational numbers obtained by stopping the continued fraction at successive depths. The determinant identity below will show that the recurrence produces these fractions in lowest terms, so reducedness is a consequence rather than part of the definition. The definition identifies what is being computed, but it does not yet provide an efficient computation. Nested simplification is inefficient because every new partial quotient changes several layers of denominators, and signs or common factors are easy to mishandle when the expressions are expanded by hand. The next result gives the continuant recurrence, the basic update rule that turns the partial quotients into numerators and denominators. [quotetheorem:5501] [citeproof:5501] The recurrence gives a fast computation, but it also raises a structural question: why are the fractions it produces already reduced, and how far apart are consecutive convergents? The positivity of $a_1,\dots,a_n$ keeps the denominators positive and increasing after the first steps, while the initial values encode the first truncation as $a_0/1$. If a later partial quotient is nonpositive, this denominator behaviour can fail; for example $[1;1,-1]$ would force a zero denominator in the nested expression \begin{align*} 1+\frac{1}{1+\frac{1}{-1}}. \end{align*} If those initial values are changed, the same recurrence may produce a different sequence; for instance taking $p_{-1}=0$ would give $p_0=0$ instead of $a_0$. The recurrence itself determines the successive numerators and denominators, but it does not determine how good these fractions are as approximations, why they are reduced, or why the final-term convention gives a unique finite expansion. Reducedness and the alternating order of adjacent approximations come from a determinant identity for neighbouring numerator-denominator pairs. [explanation: Continuant Determinant Identity] With the same integer recurrence as above, the neighbouring convergents satisfy \begin{align*} p_kq_{k-1}-p_{k-1}q_k=(-1)^{k-1} \end{align*} for every $k\geq 1$. This follows by subtracting the same expression one step earlier: \begin{align*} p_kq_{k-1}-p_{k-1}q_k =-(p_{k-1}q_{k-2}-p_{k-2}q_{k-1}). \end{align*} The base case $k=1$ is \begin{align*} p_1q_0-p_0q_1=1, \end{align*} so the sign alternates at each step. [/explanation] The determinant identity has two immediate consequences. First, $\gcd(p_k,q_k)=1$, since any common divisor must divide $1$. Second, adjacent convergents satisfy \begin{align*} \frac{p_k}{q_k}-\frac{p_{k-1}}{q_{k-1}}=\frac{(-1)^{k-1}}{q_kq_{k-1}}. \end{align*} The identity depends on using adjacent pairs generated by the continuant recurrence; unrelated reduced fractions need not have determinant $\pm 1$, as $1/2$ and $3/8$ give $1\cdot 8-3\cdot 2=2$. A counterexample to any converse is that determinant $\pm 1$ alone does not specify the partial quotients or the ambient continued fraction, since many adjacent pairs in the Stern-Brocot tree have determinant $\pm 1$ without being chosen as neighbours in a fixed continued-fraction expansion. The theorem also does not estimate the error between a convergent and the final value $[a_0;\dots,a_n]$ except for adjacent truncations. Its alternating behaviour will be essential when infinite continued fractions are introduced, where the determinant identity becomes the algebra behind convergence and best-approximation results. ## Matrix Products and Continuants The recurrence relations ask for a structural explanation: why should the same two-term update govern both numerators and denominators? Matrices give a compact answer. Each partial quotient contributes one elementary matrix, and the product stores two consecutive convergents at once. [definition: Continuant Matrix] Define the map $M:\mathbb Z\to \operatorname{Mat}_2(\mathbb Z)$ as follows: $M(a)$ is the $2\times 2$ integer matrix whose first row is $(a,1)$ and whose second row is $(1,0)$. For a finite list $a_0,\dots,a_n$, the associated continuant matrix product is \begin{align*} M(a_0)M(a_1)\cdots M(a_n). \end{align*} [/definition] This definition packages the recurrence as multiplication of columns. Since $\det M(a)=-1$, it suggests that the determinant identity should be read as a determinant computation for a product. The remaining obstruction is to check that the matrix entries are not merely analogous to convergents, but are exactly the adjacent numerators and denominators produced by the recurrence. [quotetheorem:5502] [citeproof:5502] The matrix formula is often the cleanest way to remember the signs. Its hypotheses are doing real work: the factors must be multiplied in the order of the partial quotients, since matrix multiplication is not commutative and reversing the order changes the entries. The special form of $M(a)$ is also essential; replacing the lower-left entry by $0$ would make every factor singular and would lose the determinant information entirely. The formula does not say that every product of matrices with the same determinant pattern comes from a continued fraction, nor does it by itself prove any limiting behaviour for infinite products. Its role here is organizational: it packages the recurrence and determinant identity into one reusable object. ## Rational Approximations from Truncation The final question in this chapter is why the intermediate fractions matter. A continued fraction is not only a representation of a rational number; its truncations often give unexpectedly good approximations to nearby real quantities. This phenomenon is visible even before the general best-approximation theorems are proved. [example: The Approximation 355 Over 113] The decimal expansion \begin{align*} \pi=3.14159265\dots \end{align*} suggests that $355/113$ is close to $\pi$, but the continued-fraction reason can be checked without guessing from decimals. First, \begin{align*} [3;7,16]=3+\frac{1}{7+\frac{1}{16}}. \end{align*} Since \begin{align*} 7+\frac{1}{16}=\frac{7\cdot 16+1}{16}=\frac{113}{16}, \end{align*} we get \begin{align*} [3;7,16]=3+\frac{16}{113}=\frac{3\cdot 113+16}{113}=\frac{355}{113}. \end{align*} The same rational number appears as the truncation just before the large partial quotient in \begin{align*} \pi=[3;7,15,1,292,\dots]. \end{align*} Indeed, \begin{align*} 15+\frac{1}{1}=16, \end{align*} so \begin{align*} [3;7,15,1]=3+\frac{1}{7+\frac{1}{15+\frac{1}{1}}}=3+\frac{1}{7+\frac{1}{16}}=[3;7,16]=\frac{355}{113}. \end{align*} To see the effect of the next partial quotient, write the remaining tail after the $1$ as $T=[292;\dots]$. Since the first term of this tail is $292$, we have $T>292$. Also, \begin{align*} [3;7,15]=3+\frac{1}{7+\frac{1}{15}}=3+\frac{1}{\frac{106}{15}}=3+\frac{15}{106}=\frac{333}{106}. \end{align*} Using the adjacent convergents $355/113$ and $333/106$, the continued fraction with tail $T$ is \begin{align*} [3;7,15,1,T]=\frac{355T+333}{113T+106}. \end{align*} Therefore \begin{align*} \frac{355}{113}-\pi=\frac{355}{113}-\frac{355T+333}{113T+106}. \end{align*} Putting the two fractions over a common denominator gives \begin{align*} \frac{355}{113}-\pi=\frac{355(113T+106)-113(355T+333)}{113(113T+106)}. \end{align*} Expanding the numerator, \begin{align*} 355(113T+106)-113(355T+333)=40115T+37630-40115T-37629=1. \end{align*} Hence \begin{align*} \frac{355}{113}-\pi=\frac{1}{113(113T+106)}. \end{align*} Since $T>292$, \begin{align*} \frac{1}{113(113T+106)}<\frac{1}{113(113\cdot 292+106)}=\frac{1}{3740526}. \end{align*} Thus $355/113$ is natural not because its decimal expansion was guessed, but because it is the convergent immediately before an unusually large next partial quotient. [/example] This example previews the central theme of the course. Continued fractions turn approximation into arithmetic: the size and position of the partial quotients control the quality of the convergents. This is why the same elementary construction appears later in Diophantine approximation, the geometry of the modular group, and algorithms for solving linear congruences. The next chapter passes from finite expansions of rationals to infinite expansions of irrational [real numbers](/page/Real%20Numbers), where convergence and uniqueness become the main issues. # 2. Infinite Continued Fractions and Irrational Numbers This chapter turns finite continued fractions into an infinite process. The Euclidean algorithm stops exactly when the input is rational; for an irrational number there is no final remainder, so the same division step produces an infinite list of partial quotients. The main questions are whether this infinite expression converges back to the original number, how fast its convergents approach it, and whether two different infinite lists could represent the same irrational. ## Running the Continued Fraction Algorithm Forever How can the Euclidean algorithm be continued when there is no terminal remainder? The answer is to separate the integer part from the fractional part at each stage, then invert the fractional part. For rational inputs this procedure eventually hits an integer; for irrational inputs it never does, and the successive numbers produced by the algorithm record the complete quotients. [definition: Complete Quotients And Partial Quotients] Let $\theta \in \mathbb R$. Define $\theta_0 = \theta$ and $a_0 = \lfloor \theta_0 \rfloor$. If $\theta_n \notin \mathbb Z$, define \begin{align*} \theta_{n+1} &= \frac{1}{\theta_n - a_n}, & a_{n+1} &= \lfloor \theta_{n+1} \rfloor. \end{align*} The numbers $\theta_n$ are the complete quotients, and the integers $a_n$ are the partial quotients. [/definition] The definition isolates the same operation used in the Euclidean algorithm: subtract the largest integer not exceeding the current number and invert what remains. Once $n \ge 1$, the complete quotient satisfies $\theta_n > 1$, so $a_n \in \mathbb N$. This positivity is the arithmetic constraint that makes simple continued fractions rigid. [definition: Infinite Simple Continued Fraction] An infinite simple continued fraction is an expression \begin{align*} [a_0; a_1, a_2, \dots] = a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{a_3 + \cdots}}}, \end{align*} where $a_0 \in \mathbb Z$ and $a_n \in \mathbb N$ for every $n \ge 1$. [/definition] The expression records an infinite arithmetic recipe, but the recipe is not yet a real number. To test convergence, we need finite approximations that can be compared using the recurrence and determinant identities from the previous chapter. These finite truncations are the convergents. [definition: Convergents Of An Infinite Continued Fraction] Let $[a_0; a_1, a_2, \dots]$ be an infinite simple continued fraction. Its $n$th convergent is \begin{align*} \frac{p_n}{q_n} = [a_0; a_1, \dots, a_n], \end{align*} where $p_n$ and $q_n$ are defined by \begin{align*} p_{-2} &= 0, & p_{-1} &= 1, & p_n &= a_n p_{n-1} + p_{n-2}. \end{align*} Also, \begin{align*} q_{-2} &= 1, & q_{-1} &= 0, & q_n &= a_n q_{n-1} + q_{n-2}. \end{align*} [/definition] The recurrence lets us work with infinite continued fractions without manipulating an infinite nested denominator directly. As in Chapter 1, the determinant identity from finite continued fractions remains the basic algebraic control on the sequence of convergents. [quotetheorem:1759] [citeproof:1759] The identity shows in particular that consecutive convergents are distinct and already in lowest terms. The hypotheses behind it are important: the recurrence must use the same partial quotients in both numerator and denominator, and the initial conditions must be the continuant initial conditions above. For instance, if the denominator recurrence were started with $q_{-2}=0$ and $q_{-1}=1$ while the numerator recurrence kept the usual initial conditions, then at $n=0$ the determinant would be \begin{align*} p_0q_{-1}-p_{-1}q_0=a_0, \end{align*} not the required value $-1$. The identity is algebraic rather than analytic, so by itself it does not say that the convergents approach a limit; it only says that neighbouring convergents differ by exactly the reciprocal of a product of denominators. Convergence will require a separate argument that those denominators become large. [example: First Convergents Of Square Root Two] Let $\theta=\sqrt{2}$. Since $1<\sqrt{2}<2$, the first partial quotient is $a_0=\lfloor\sqrt{2}\rfloor=1$. The first complete quotient is \begin{align*} \theta_1=\frac{1}{\sqrt{2}-1}. \end{align*} Rationalizing the denominator gives \begin{align*} \theta_1=\frac{1}{\sqrt{2}-1}\cdot\frac{\sqrt{2}+1}{\sqrt{2}+1}=\frac{\sqrt{2}+1}{2-1}=\sqrt{2}+1. \end{align*} Because $2<\sqrt{2}+1<3$, we have $a_1=\lfloor\theta_1\rfloor=2$. Now subtract $a_1$ and invert: \begin{align*} \theta_2=\frac{1}{\theta_1-a_1}=\frac{1}{(\sqrt{2}+1)-2}=\frac{1}{\sqrt{2}-1}=\sqrt{2}+1. \end{align*} Thus $\theta_2=\theta_1$, so the same calculation repeats at every later stage. Hence $a_n=2$ for every $n\ge 1$, and \begin{align*} \sqrt{2}=[1;2,2,2,\dots]=[1;\overline{2}]. \end{align*} Using the convergent recurrences with $p_{-2}=0$, $p_{-1}=1$, $q_{-2}=1$, and $q_{-1}=0$, the first convergent is \begin{align*} p_0=1\cdot 1+0=1,\qquad q_0=1\cdot 0+1=1. \end{align*} Since $a_1=a_2=a_3=2$, the next three pairs are \begin{align*} p_1=2\cdot 1+1=3,\qquad q_1=2\cdot 1+0=2. \end{align*} \begin{align*} p_2=2\cdot 3+1=7,\qquad q_2=2\cdot 2+1=5. \end{align*} \begin{align*} p_3=2\cdot 7+3=17,\qquad q_3=2\cdot 5+2=12. \end{align*} Therefore the first convergents are \begin{align*} 1,\quad \frac{3}{2},\quad \frac{7}{5},\quad \frac{17}{12}. \end{align*} They alternate around $\sqrt{2}$ because all four numbers are positive and their squares compare with $2$ as follows: \begin{align*} 1^2=1<2. \end{align*} \begin{align*} \left(\frac{3}{2}\right)^2=\frac{9}{4}>2. \end{align*} \begin{align*} \left(\frac{7}{5}\right)^2=\frac{49}{25}<2. \end{align*} \begin{align*} \left(\frac{17}{12}\right)^2=\frac{289}{144}>2. \end{align*} So $1$ and $7/5$ are below $\sqrt{2}$, while $3/2$ and $17/12$ are above it. [/example] This example displays the recurring pattern that will later become the theory of quadratic irrationals. For now its role is simpler: it shows that a repeating infinite expansion can be generated directly by the floor map. ## Convergence Of Infinite Continued Fractions Why should the convergents of an arbitrary infinite continued fraction approach a limit? The determinant identity says successive convergents become close provided the denominators grow. Since every later partial quotient is positive, the denominators grow at least as fast as the Fibonacci recurrence, so the gaps between neighbouring convergents shrink to zero. [quotetheorem:5503] [citeproof:5503] Large denominators turn the determinant identity into a metric estimate, but the positivity of the partial quotients is doing essential work here. If zero or negative later partial quotients were allowed, the recurrence could stagnate, cancel, or even produce zero denominators. For example, taking $a_1=0$ gives \begin{align*} q_1=a_1q_0+q_{-1}=0, \end{align*} so the first nonzero convergent denominator already disappears. Taking $a_1=1$ and $a_2=-1$ gives \begin{align*} q_2=-q_1+q_0=0. \end{align*} In such cases the determinant identity would no longer force small gaps between neighbouring convergents. Growth alone also does not identify the eventual limit with any number from which the continued fraction algorithm began; it only prepares the convergence argument for a formally specified infinite list. The next theorem says that such a list has convergent finite truncations, so an infinite simple continued fraction denotes a real number. [quotetheorem:5504] [citeproof:5504] The theorem gives more than existence of a limit: it gives a geometric picture. The convergents form alternating lower and upper bounds whose intervals shrink around a single real number. The simple continued fraction hypotheses are what make this picture reliable: positivity gives growing denominators, while the continuant determinant controls the width of the enclosing intervals. Without positivity, the formal expression may not define a real number at all; for instance $[0;1,-1,1,\dots]$ already produces $q_2=0$, so the second convergent is undefined. At this stage, however, the result is still only about a formal infinite list of integers; it has not yet shown that applying the algorithm to an irrational number returns that original number. To use the bracket notation as a genuine equality rather than a formal symbol, we now declare that this common limit is the value of the infinite continued fraction. [definition: Value Of An Infinite Continued Fraction] The value of the infinite simple continued fraction $[a_0;a_1,a_2,\dots]$ is \begin{align*} \lim_{n\to\infty}\frac{p_n}{q_n}, \end{align*} where $p_n/q_n=[a_0;a_1,\dots,a_n]$. [/definition] With this definition in place, an infinite continued fraction is no longer just formal notation. It is a recipe producing a real number by rational approximations. [example: The Golden Ratio] Let \begin{align*} \varphi=\frac{1+\sqrt{5}}{2}. \end{align*} Since $1<\sqrt{5}<3$, we have \begin{align*} 1<\frac{1+\sqrt{5}}{2}<2, \end{align*} so $a_0=\lfloor\varphi\rfloor=1$. We first verify the identity that makes the continued fraction repeat. Expanding the square gives \begin{align*} \varphi^2=\left(\frac{1+\sqrt{5}}{2}\right)^2=\frac{1+2\sqrt{5}+5}{4}=\frac{6+2\sqrt{5}}{4}=\frac{3+\sqrt{5}}{2}. \end{align*} On the other hand, \begin{align*} \varphi+1=\frac{1+\sqrt{5}}{2}+1=\frac{1+\sqrt{5}+2}{2}=\frac{3+\sqrt{5}}{2}. \end{align*} Thus $\varphi^2=\varphi+1$. Since $\varphi>0$, dividing by $\varphi$ gives \begin{align*} \varphi=1+\frac{1}{\varphi}. \end{align*} Subtracting $1$ from both sides gives \begin{align*} \varphi-1=\frac{1}{\varphi}. \end{align*} Therefore the first complete quotient is \begin{align*} \theta_1=\frac{1}{\varphi-a_0}=\frac{1}{\varphi-1}=\frac{1}{1/\varphi}=\varphi. \end{align*} Since $\theta_1=\varphi$ and $\lfloor\varphi\rfloor=1$, the same floor-and-invert step repeats at every stage. Hence $a_n=1$ for every $n\ge 0$, and \begin{align*} \varphi=[1;1,1,1,\dots]=[1;\overline{1}]. \end{align*} Using the convergent recurrences with $a_n=1$ for every $n$, and with $p_{-2}=0$, $p_{-1}=1$, $q_{-2}=1$, and $q_{-1}=0$, the first convergent is \begin{align*} p_0=1\cdot p_{-1}+p_{-2}=1\cdot1+0=1,\qquad q_0=1\cdot q_{-1}+q_{-2}=1\cdot0+1=1. \end{align*} The next four pairs are \begin{align*} p_1=1\cdot p_0+p_{-1}=1+1=2,\qquad q_1=1\cdot q_0+q_{-1}=1+0=1. \end{align*} \begin{align*} p_2=1\cdot p_1+p_0=2+1=3,\qquad q_2=1\cdot q_1+q_0=1+1=2. \end{align*} \begin{align*} p_3=1\cdot p_2+p_1=3+2=5,\qquad q_3=1\cdot q_2+q_1=2+1=3. \end{align*} \begin{align*} p_4=1\cdot p_3+p_2=5+3=8,\qquad q_4=1\cdot q_3+q_2=3+2=5. \end{align*} Thus the first convergents are \begin{align*} 1,\quad \frac{2}{1},\quad \frac{3}{2},\quad \frac{5}{3},\quad \frac{8}{5}. \end{align*} The numerator and denominator sequences both obey the Fibonacci recurrence $x_n=x_{n-1}+x_{n-2}$, shifted by one index, because every recurrence coefficient is $a_n=1$. [/example] The golden ratio is the slowest-growing case for denominators, because all positive partial quotients are as small as possible. This makes it the limiting model for several later sharp approximation results. ## Recovering An Irrational From Its Complete Quotients Suppose the continued fraction algorithm is applied to a real number $\theta$. The finite convergents approximate $\theta$, but the complete quotient $\theta_{n+1}$ also contains the exact tail of the expansion. The next identity links the exact number to its $n$th convergent and the next complete quotient. [quotetheorem:1758] [citeproof:1758] This formula is the exact bridge between the algorithm and convergence, because it keeps the unfinished tail rather than discarding it. Its hypotheses matter: the complete quotient $\theta_{n+1}$ must be the actual tail produced by the floor-and-invert algorithm, not an arbitrary real number inserted into the last slot. The formula is also not an estimate by itself; if the denominator $q_n\theta_{n+1}+q_{n-1}$ were allowed to be small, the identity would give no useful approximation statement. The convergence theorem for formal infinite lists therefore still leaves one decisive question: when the list comes from an irrational input $\theta$, do the rational [convergents converge](/theorems/1760) to that same $\theta$ rather than merely to some value attached to the list? For simple continued fractions of irrationals, the positivity of the actual complete quotients prevents denominator collapse and lets the determinant identity turn the formula into the needed error estimate. [quotetheorem:1760] [citeproof:1760] The theorem justifies the notation $\theta=[a_0;a_1,a_2,\dots]$ for irrational $\theta$. For approximation theory, convergence alone is too coarse: we need a numerical bound that can be compared against other rational approximations with similar denominators. The same exact error computation gives such a bound in terms of two consecutive convergent denominators. [quotetheorem:5505] [citeproof:5505] This estimate is the first sign that continued fractions are unusually good rational approximations. The irrationality assumption ensures that there is always a next complete quotient, so $q_{n+1}$ is defined for every $n$ and the strict inequality comes from the nonzero fractional tail beyond $a_{n+1}$. For a finite rational expansion, the last convergent is exactly equal to the number, and the displayed bound is not the right way to describe the terminal step. The estimate also does not yet say that convergents are best possible among all rationals; it only gives a uniform upper bound for this particular sequence of approximations. Chapter 4 will compare it with what arbitrary rational numbers can achieve under denominator bounds. [example: The Expansion Of Square Root Three] Let $\theta=\sqrt{3}$. Since $1<\sqrt{3}<2$, the first partial quotient is $a_0=\lfloor\sqrt{3}\rfloor=1$. The first complete quotient is \begin{align*} \theta_1=\frac{1}{\sqrt{3}-1}. \end{align*} Rationalizing the denominator gives \begin{align*} \theta_1=\frac{1}{\sqrt{3}-1}\cdot\frac{\sqrt{3}+1}{\sqrt{3}+1}=\frac{\sqrt{3}+1}{3-1}=\frac{\sqrt{3}+1}{2}. \end{align*} Because $1<\sqrt{3}<3$, adding $1$ and dividing by $2$ gives \begin{align*} 1<\frac{\sqrt{3}+1}{2}<2, \end{align*} so $a_1=\lfloor\theta_1\rfloor=1$. Now subtract $a_1$ and invert: \begin{align*} \theta_2=\frac{1}{\theta_1-a_1}=\frac{1}{\frac{\sqrt{3}+1}{2}-1}=\frac{1}{\frac{\sqrt{3}-1}{2}}=\frac{2}{\sqrt{3}-1}. \end{align*} Rationalizing again, \begin{align*} \theta_2=\frac{2}{\sqrt{3}-1}\cdot\frac{\sqrt{3}+1}{\sqrt{3}+1}=\frac{2(\sqrt{3}+1)}{3-1}=\sqrt{3}+1. \end{align*} Since $1<\sqrt{3}<2$, we have \begin{align*} 2<\sqrt{3}+1<3, \end{align*} so $a_2=\lfloor\theta_2\rfloor=2$. The next step returns to the previous complete quotient: \begin{align*} \theta_3=\frac{1}{\theta_2-a_2}=\frac{1}{(\sqrt{3}+1)-2}=\frac{1}{\sqrt{3}-1}=\frac{\sqrt{3}+1}{2}=\theta_1. \end{align*} Thus the complete quotients repeat in the pattern $\theta_1,\theta_2,\theta_1,\theta_2,\dots$, and the partial quotients repeat in the pattern $1,2,1,2,\dots$ after $a_0$. Hence \begin{align*} \sqrt{3}=[1;1,2,1,2,\dots]=[1;\overline{1,2}]. \end{align*} Using the convergent recurrences with $p_{-2}=0$, $p_{-1}=1$, $q_{-2}=1$, and $q_{-1}=0$, the first convergent is \begin{align*} p_0=1\cdot1+0=1,\qquad q_0=1\cdot0+1=1. \end{align*} Since $a_1=1$, $a_2=2$, and $a_3=1$, the next three pairs are \begin{align*} p_1=1\cdot1+1=2,\qquad q_1=1\cdot1+0=1. \end{align*} \begin{align*} p_2=2\cdot2+1=5,\qquad q_2=2\cdot1+1=3. \end{align*} \begin{align*} p_3=1\cdot5+2=7,\qquad q_3=1\cdot3+1=4. \end{align*} Therefore the first convergents are \begin{align*} 1,\quad 2,\quad \frac{5}{3},\quad \frac{7}{4}. \end{align*} They alternate around $\sqrt{3}$ because all four numbers are positive and their squares compare with $3$ as follows: \begin{align*} 1^2=1<3. \end{align*} \begin{align*} 2^2=4>3. \end{align*} \begin{align*} \left(\frac{5}{3}\right)^2=\frac{25}{9}<3, \end{align*} since $25<27$, and \begin{align*} \left(\frac{7}{4}\right)^2=\frac{49}{16}>3, \end{align*} since $49>48$. Thus $1$ and $5/3$ are below $\sqrt{3}$, while $2$ and $7/4$ are above it. [/example] This example is less symmetric than $\sqrt{2}$, but it shows the same mechanism: a quadratic identity causes complete quotients to repeat. Periodicity is the subject of Chapter 6, after Chapter 4 develops the approximation properties of convergents. ## Uniqueness Of Infinite Expansions Could two different infinite simple continued fractions converge to the same irrational number? The floor map prevents this. The first partial quotient is forced by the integer part of the number, and after removing that integer part and inverting, the same argument applies to the tail. [quotetheorem:5506] [citeproof:5506] The irrational hypothesis matters because finite continued fractions have the familiar terminal ambiguity $[a_0;\dots,a_n]=[a_0;\dots,a_n-1,1]$ when $a_n>1$. Infinite expansions avoid this ambiguity: there is no last partial quotient to modify. [remark: Rational Numbers And Termination] For rational $\theta$, the continued fraction algorithm terminates because it is the Euclidean algorithm in another form. The finite expansion is unique after imposing the convention that the final partial quotient is greater than $1$, except for the single-integer case. Thus rationals correspond to finite simple continued fractions, while irrationals correspond to infinite simple continued fractions. [/remark] The chapter has now established the basic dictionary. Irrational numbers are exactly the real numbers whose simple continued fraction algorithm runs forever, and the resulting convergents converge back to the starting number with the sharp elementary estimate \begin{align*} \left|\theta-\frac{p_n}{q_n}\right|<\frac{1}{q_nq_{n+1}}. \end{align*} The next step is to ask why these convergents are not merely good approximations, but best approximations among rationals with bounded denominator. # 3. Arithmetic and Geometry of Convergents Continued fractions turn approximation into a sequence of exact arithmetic tests. This chapter studies the convergents \begin{align*} \frac{p_n}{q_n} \end{align*} attached to an irrational simple continued fraction $\theta=[a_0;a_1,a_2,\dots]$. The required background is the definition of a simple continued fraction, the recurrence defining $p_n$ and $q_n$, and the continuant determinant identity from Chapters 1 and 2. The aim is to refine convergence into arithmetic and geometric structure: which side of $\theta$ each convergent lies on, how the even and odd subsequences move, and why adjacent convergents span the smallest possible parallelograms in $\mathbb Z^2$. These facts prepare the best-approximation theory by showing that convergents are not only close to $\theta$, but also rigidly positioned among rational numbers with small denominators. ## Alternation and Monotonicity of Convergents The first problem is not merely whether the sequence of convergents converges to $\theta$, but how it converges. A decimal approximation may approach from one side for a long time; continued fraction convergents behave more rigidly, alternating around the target and tightening the interval at each step. Recall the recurrence relations from the first chapter. They are \begin{align*} p_n = a_n p_{n-1} + p_{n-2} \end{align*} and \begin{align*} q_n = a_n q_{n-1} + q_{n-2}, \end{align*} with initial values $p_{-2}=0$, $p_{-1}=1$, $q_{-2}=1$, and $q_{-1}=0$. For a simple continued fraction, $a_n \in \mathbb N$ for $n \ge 1$, so the denominators are positive once $n \ge 0$. [quotetheorem:5507] [citeproof:5507] This formula shows that the consecutive jumps shrink at least as fast as the reciprocal of a product of denominators. The identity itself is not where irrationality is used: the same determinant calculation applies to any finite stretch of continued-fraction recurrence data with nonzero denominators. Irrationality matters for the surrounding chapter because it gives an infinite sequence of adjacent convergents and hence an endless chain of shrinking brackets. The positivity of the denominators is essential for the oriented version of the displayed formula: without fixing $q_n>0$, the same rational could be represented with the opposite denominator sign and the displayed orientation would lose its meaning. The statement is also special to consecutive convergents; unrelated reduced fractions such as \begin{align*} \frac{1}{2} \quad \text{and} \quad \frac{2}{5} \end{align*} have determinant $1$, but they need not occur as adjacent approximants to a given irrational. The alternating sign now raises the next ordering question: if consecutive jumps alternate sign, what happens when we compare every second convergent rather than adjacent ones? [quotetheorem:5508] [citeproof:5508] The theorem says that continued fractions produce two rational fences, one moving upward and one moving downward. Irrationality is part of the point here: for a finite continued fraction representing a rational number, the process terminates and there are not two infinite subsequences converging from opposite sides. The positivity of the partial quotients after $a_0$ is also doing real work. For example, if the same recurrence is allowed to use the signed data \begin{align*} a_0=0,\qquad a_1=2,\qquad a_2=-1, \end{align*} then the first three formal convergents are \begin{align*} 0,\qquad \frac{1}{2},\qquad 1, \end{align*} so the even term at stage $2$ has crossed above the odd term at stage $1$. Thus the simple bracketing order is a feature of simple continued fractions, not of arbitrary recurrence data. This two-fence picture is still incomplete until we locate $\theta$ relative to the fences. Monotonicity only compares rational endpoints with each other: it tells us that the even endpoints move upward, the odd endpoints move downward, and the two chains do not cross. It does not by itself say that $\theta$ is between the two chains at every finite stage, nor does it identify which side of $\theta$ a given convergent occupies. Those omissions matter because later error estimates use the interval between two consecutive convergents as a certified enclosure for $\theta$, not merely as a short rational interval whose endpoints happen to be ordered. To turn the ordering theorem into an approximation theorem, we must compare $\theta$ with the same rational endpoints that monotonicity has already ordered. The next theorem supplies exactly that local bracketing statement: every adjacent pair already traps $\theta$, so the rational fences are known to enclose the irrational target at each step. For this comparison, write the complete quotient after the $n$th partial quotient as $\theta_{n+1}=[a_{n+1};a_{n+2},a_{n+3},\dots]$. With this convention, replacing $a_{n+1}$ by the variable $\theta_{n+1}$ in the finite continuant formula reconstructs the original irrational $\theta$. This reconstruction is needed because the previous monotonicity theorem only orders convergents among themselves; it does not yet certify that the irrational target sits inside each adjacent rational interval. The next theorem supplies that missing comparison with $\theta$, turning the two monotone rational fences into genuine enclosing intervals that later error estimates can use. [quotetheorem:1758] [citeproof:1758] This result turns convergence into an interval method. The irrationality hypothesis is necessary for strict containment: if the continued fraction terminates, the final convergent equals the number and there is no strict interval at that endpoint. The statement is also stronger than ordinary convergence, since a convergent sequence can approach a limit from one side only and still converge. Here each adjacent pair gives a rational interval containing $\theta$, and the interval length is exactly \begin{align*} \frac{1}{q_nq_{n+1}}. \end{align*} A concrete quadratic irrational shows how the bounds are read from the recurrence. [example: Locating Square Root Five] Since \begin{align*} \sqrt{5}=2+(\sqrt{5}-2), \end{align*} we have $a_0=2$. The next complete quotient is obtained by inverting the fractional part: \begin{align*} \frac{1}{\sqrt{5}-2}=\frac{\sqrt{5}+2}{(\sqrt{5}-2)(\sqrt{5}+2)}=\frac{\sqrt{5}+2}{5-4}=\sqrt{5}+2=4+(\sqrt{5}-2). \end{align*} Thus the same fractional part $\sqrt{5}-2$ repeats after the partial quotient $4$, so \begin{align*} \sqrt{5}=[2;4,4,4,\dots]. \end{align*} Using $p_n=a_np_{n-1}+p_{n-2}$ and $q_n=a_nq_{n-1}+q_{n-2}$ with $a_0=2$ and $a_n=4$ for $n\ge 1$, the first convergent is \begin{align*} \frac{p_0}{q_0}=\frac{2}{1}=2. \end{align*} The next four are \begin{align*} \frac{p_1}{q_1}=\frac{4\cdot 2+1}{4\cdot 1+0}=\frac{9}{4}, \end{align*} \begin{align*} \frac{p_2}{q_2}=\frac{4\cdot 9+2}{4\cdot 4+1}=\frac{38}{17}, \end{align*} \begin{align*} \frac{p_3}{q_3}=\frac{4\cdot 38+9}{4\cdot 17+4}=\frac{161}{72}, \end{align*} and \begin{align*} \frac{p_4}{q_4}=\frac{4\cdot 161+38}{4\cdot 72+17}=\frac{682}{305}. \end{align*} By the monotonicity theorem above, the even convergents \begin{align*} 2,\quad \frac{38}{17},\quad \frac{682}{305},\dots \end{align*} increase, while the odd convergents \begin{align*} \frac{9}{4},\quad \frac{161}{72},\dots \end{align*} decrease. The exact reconstruction formula above places $\sqrt{5}$ between each adjacent pair of convergents, so it lies between $\frac{38}{17}$ and $\frac{161}{72}$. Their order is determined by putting them over the common denominator $17\cdot 72=1224$: \begin{align*} \frac{161}{72}-\frac{38}{17}=\frac{161\cdot 17-38\cdot 72}{72\cdot 17}. \end{align*} The numerator is \begin{align*} 161\cdot 17-38\cdot 72=2737-2736=1, \end{align*} so \begin{align*} \frac{161}{72}-\frac{38}{17}=\frac{1}{1224}>0. \end{align*} Therefore \begin{align*} \frac{38}{17}<\sqrt{5}<\frac{161}{72}. \end{align*} The certified bracket length is $1/1224$, matching the consecutive-difference formula because $q_2q_3=17\cdot 72=1224$. Thus the continued-fraction recurrence gives rational upper and lower bounds for $\sqrt{5}$ without using a decimal expansion. [/example] The example makes the role of denominators visible: the certified interval is small because $17$ and $72$ are already moderately large. This motivates a general growth estimate for $q_n$, since denominator growth controls the speed at which the bracketing intervals shrink. [explanation: Denominator Growth Reminder] For an infinite simple continued fraction, the denominator recurrence satisfies \begin{align*} q_{n+1}\geq q_n+q_{n-1} \end{align*} once $n\geq1$. Thus the denominators tend to infinity, and the interval lengths controlled by products such as $q_nq_{n+1}$ shrink. [/explanation] The Fibonacci lower bound is the slowest possible denominator growth, occurring for the continued fraction with all partial quotients equal to $1$. The assumptions $a_n\ge 1$ and infinitude are essential: allowing zero or negative partial quotients would break the recurrence comparison, while a finite continued fraction gives only finitely many denominators. The result is only a lower bound, so it does not predict where unusually large partial quotients occur; it says that even in the slowest case the bracketing intervals must shrink quickly. Large partial quotients create sudden jumps in the denominators and correspond to especially sharp individual approximations. ## Primitive Lattice Vectors and Determinants The second problem is to explain why convergents are arithmetically special among rational approximations. A rational number written in the form \begin{align*} \frac{p}{q} \end{align*} can be represented by the integer vector $(q,p) \in \mathbb Z^2$, and the determinant of two such vectors measures the signed area of the parallelogram they span. Consecutive convergents have determinant $\pm 1$, the smallest nonzero area possible in the integer lattice. Equivalently, the adjacent convergent matrices are unimodular: they have integer entries and determinant $\pm1$. This is the same integer-lattice geometry that underlies modular transformations and Farey tessellations. Before using lattice areas, we need to isolate the integer vectors that represent rationals in lowest terms. Without this restriction, the same rational slope has many lattice representatives: \begin{align*} \frac{1}{2} \end{align*} can be represented by $(2,1)$, $(4,2)$, or $(6,3)$, and the determinant with another vector changes under this scaling even though the rational number has not changed. Thus a lattice statement about rational approximations would be meaningless unless each slope is represented by its smallest integer vector. The relevant condition is primitivity: a vector is not an integer multiple $k v$ of another lattice vector with $|k|>1$. [definition: Primitive Integer Vector] A nonzero integer vector $(q,p) \in \mathbb Z^2$ is primitive if $\gcd(p,q)=1$. [/definition] Primitive vectors correspond to rational numbers written in lowest terms. For convergents, the lattice viewpoint would break down if a numerator and denominator had a common factor, because the vector $(q_n,p_n)$ would not be the smallest integer vector on its slope. The first lattice question is therefore whether the continued-fraction construction automatically chooses primitive representatives. If it did not, later determinant and area arguments would be contaminated by an arbitrary common scaling factor rather than reflecting the rational approximation itself. [quotetheorem:5509] [citeproof:5509] Reducedness tells us that each convergent gives a primitive lattice vector, but this is only a single-vector condition. The continued-fraction hypotheses matter: the arbitrary rational approximation $2/4$ to $\theta$ represents the same slope as $1/2$ but gives the non-primitive vector $(4,2)$, so it would not support a lattice-area argument. Even among reduced fractions, the condition does not control how two slopes sit relative to each other, nor does it imply that either fraction is a good approximation to $\theta$. For instance, many reduced fractions can lie in the same small interval if their denominators are allowed to be large. The next question is stronger and genuinely two-dimensional: what is the determinant of two adjacent primitive vectors coming from consecutive convergents? [quotetheorem:5510] [citeproof:5510] The unit determinant result upgrades reducedness to a relation between two neighbouring fractions, but it must be interpreted with the correct denominator scale. Reducedness alone does not prevent other reduced fractions from lying between two slopes: for instance \begin{align*} \frac{1}{3} \quad \text{and} \quad \frac{2}{5} \end{align*} are reduced, but pairs with larger determinant leave room for additional lattice points and hence additional rational competitors. A concrete failure is \begin{align*} \frac{1}{3}<\frac{1}{2}<\frac{3}{5}, \end{align*} where the endpoint determinant has absolute value \begin{align*} |1\cdot 5-3\cdot 3|=4. \end{align*} This shows why reducedness by itself is too weak. By contrast, the determinant condition $|ad-bc|=1$ says that the two primitive vectors form a smallest possible lattice cell. It does not mean that there are no reduced fractions between the two slopes: the mediant lies between them. The useful exclusion is subtler and denominator-sensitive: no reduced fraction with denominator at most the larger endpoint denominator can lie strictly between two Farey neighbours. To use that relation in later comparisons with arbitrary rationals, we need a name for reduced pairs whose cross-determinant has the smallest possible nonzero absolute value; this motivates the Farey-neighbour definition. [definition: Farey Neighbours] Two reduced rational numbers \begin{align*} \frac{a}{b} \quad \text{and} \quad \frac{c}{d}, \end{align*} with $b,d>0$, are Farey neighbours if \begin{align*} ad-bc = \pm 1. \end{align*} [/definition] The definition is symmetric up to sign. In lattice terms, the vectors $(b,a)$ and $(d,c)$ form a basis of $\mathbb Z^2$ after possibly changing orientation, so consecutive convergents should now fit the Farey-neighbour definition. [quotetheorem:5511] [citeproof:5511] Farey neighbours have no lattice point strictly inside the fundamental parallelogram they determine. The hypotheses in the definition prevent two common ambiguities. Reducedness is needed because the unreduced representative $2/4$ of $1/2$ changes the determinant with $3/5$ from \begin{align*} 1\cdot 5-2\cdot 3=-1 \end{align*} to \begin{align*} 2\cdot 5-4\cdot 3=-2, \end{align*} even though the slope has not changed. Positive denominators are needed so that each rational has a fixed representative and the order between slopes agrees with the usual order on fractions; replacing $3/5$ by $-3/-5$ reverses the signed determinant while leaving the rational number unchanged. If the determinant had absolute value greater than $1$, the parallelogram would have larger lattice area, and additional primitive vectors could appear between the two slopes. This is exactly the failure mode excluded by the Farey condition, and it is why Farey sequences in elementary number theory list neighbouring reduced fractions by the same determinant test. For continued fractions, this geometric obstruction is the reason that no fraction with a small denominator can slip between two adjacent convergents without paying a determinant cost. [remark: Mediants Between Farey Neighbours] If \begin{align*} \frac{a}{b}<\frac{c}{d} \end{align*} are Farey neighbours, then their mediant \begin{align*} \frac{a+c}{b+d} \end{align*} lies strictly between them. In continued fractions, intermediate fractions obtained before the next convergent often appear as repeated mediants between adjacent convergents. This observation becomes useful when proving best approximation results, because it identifies the only possible rational competitors near $\theta$. [/remark] The mediant remark is easier to remember when paired with the lattice picture: adding two primitive neighbour vectors gives the vector of the mediant. The square-root-five convergents provide a small set of vectors where both the alternating slopes and the unit parallelograms can be checked by hand. [example: Lattice Parallelograms For The Square Root Five Pattern] For $\sqrt{5}=[2;4,4,4,\dots]$, the first three convergents are \begin{align*} \frac{p_0}{q_0}=\frac{2}{1},\qquad \frac{p_1}{q_1}=\frac{9}{4},\qquad \frac{p_2}{q_2}=\frac{38}{17}. \end{align*} Thus the corresponding lattice vectors $(q_n,p_n)$ are \begin{align*} (q_0,p_0)=(1,2),\qquad (q_1,p_1)=(4,9),\qquad (q_2,p_2)=(17,38). \end{align*} The determinant of the first adjacent pair is \begin{align*} \det((1,2),(4,9))=1\cdot 9-4\cdot 2=9-8=1. \end{align*} The determinant of the next adjacent pair is \begin{align*} \det((4,9),(17,38))=4\cdot 38-17\cdot 9=152-153=-1. \end{align*} Since the area of the parallelogram spanned by two plane vectors is the absolute value of their determinant, these two adjacent pairs span lattice parallelograms of areas \begin{align*} |1|=1 \end{align*} and \begin{align*} |-1|=1. \end{align*} The signs are opposite, so the orientation alternates from the first adjacent pair to the second. The slopes of these three vectors are the convergents themselves: \begin{align*} \frac{2}{1}=2,\qquad \frac{9}{4},\qquad \frac{38}{17}. \end{align*} Their positions relative to the line of slope $\sqrt{5}$ can be checked without decimals. First, \begin{align*} 2<\sqrt{5} \end{align*} because $2>0$, $\sqrt{5}>0$, and \begin{align*} 2^2=4<5=(\sqrt{5})^2. \end{align*} Next, \begin{align*} \frac{9}{4}>\sqrt{5} \end{align*} because both numbers are positive and \begin{align*} \left(\frac{9}{4}\right)^2=\frac{81}{16}>\frac{80}{16}=5=(\sqrt{5})^2. \end{align*} Finally, \begin{align*} \frac{38}{17}<\sqrt{5} \end{align*} because both numbers are positive and \begin{align*} \left(\frac{38}{17}\right)^2=\frac{1444}{289}<\frac{1445}{289}=5=(\sqrt{5})^2. \end{align*} Thus the vectors from the origin have slopes below, above, and below the line of slope $\sqrt{5}$, while consecutive vectors span unit-area parallelograms with alternating orientation. [/example] ## The Arithmetic Meaning of the Bracketing Intervals The final question in this chapter is how the order picture and the lattice picture reinforce each other. The interval between two consecutive convergents is short because its length is \begin{align*} \frac{1}{q_nq_{n+1}}, \end{align*} and it is arithmetically rigid because the endpoints are Farey neighbours. The determinant identity already gives the exact distance between adjacent slopes. We record this as a separate theorem because it converts the lattice statement into the numerical error scale used in the next chapter. [quotetheorem:5512] [citeproof:5512] This identity sharpens the error estimate from the previous chapter. The formula depends on adjacency; for non-consecutive convergents the determinant need not have absolute value $1$, so the same denominator product would not give the interval length. It is also a length estimate for the whole bracket, not yet an estimate for either endpoint separately. The remaining step is to pass from the length of the whole bracket to the distance from $\theta$ to a single convergent, which gives the estimate used when comparing against arbitrary fractions in Diophantine approximation. [explanation: Convergent Error Bound] For an irrational simple continued fraction with convergents $p_n/q_n$, the standard error estimate gives \begin{align*} \left|\theta-\frac{p_n}{q_n}\right|<\frac{1}{q_nq_{n+1}} \end{align*} for every $n\geq0$. [/explanation] The chapter's two viewpoints now match: analytically, convergents produce nested shrinking intervals around $\theta$; arithmetically, the endpoints of those intervals are primitive lattice vectors with determinant $\pm1$. Each hypothesis has a visible job. Irrationality gives strictness: for a terminating continued fraction such as $1/2=[0;2]$, the final convergent equals the target, so the strict inequality at that endpoint would fail. Adjacency gives the exact bracket length: for $\sqrt{5}$, the non-consecutive convergents $2/1$ and $38/17$ have distance $4/17$, not $1/(1\cdot 17)$. Positivity of denominators fixes the denominator product and the orientation of the bracket; replacing a denominator by its negative represents the same rational number but destroys the convention used in the comparison. The bound is deliberately one-sided as a theorem about convergents; it does not say that every rational with a small error must be a convergent, and it does not yet exclude a non-convergent with a larger denominator from being closer. Those stronger conclusions require comparing determinants against arbitrary primitive vectors, which is the number-theoretic step behind best approximation. Chapter 4 uses this structure to compare convergents with arbitrary rationals \begin{align*} \frac{a}{b} \end{align*} and to prove that convergents give best approximations under denominator constraints. # 4. Best Rational Approximations Building on the convergence and bracketing results of Chapters 2 and 3, this chapter develops continued fractions as a tool for Diophantine approximation. The main prerequisites are the Euclidean algorithm, elementary properties of rational numbers, and the recurrence relations for continued-fraction convergents established earlier in the course. The goal is to understand not only why convergents approach an irrational number, but why they solve precise optimisation problems among rational approximations with bounded denominator. Best rational approximation asks for more than convergence. A sequence of convergents $p_n/q_n$ tends to an irrational number $\theta$, but a numerical approximation is usually chosen under a constraint: the denominator cannot exceed some bound, or the error $|q\theta-p|$ must be as small as possible among all feasible integers. This chapter explains why continued fractions solve that optimisation problem, and why the especially good rational approximations to numbers such as $\pi$ are forced to appear in the continued fraction expansion. Throughout this chapter, write the continued fraction expansion of $\theta$ as \begin{align*} \theta=[a_0;a_1,a_2,\dots], \end{align*} where $a_0\in\mathbb Z$ and $a_k\in\mathbb N$ for $k\ge1$. The convergents $p_n/q_n=[a_0;\dots,a_n]$ are generated from \begin{align*} p_{-2}=0,\quad p_{-1}=1,\qquad q_{-2}=1,\quad q_{-1}=0, \end{align*} by the recurrence \begin{align*} p_n=a_np_{n-1}+p_{n-2},\qquad q_n=a_nq_{n-1}+q_{n-2}. \end{align*} In particular $q_0=1$, and the symbol $a_{n+1}$ always denotes the next partial quotient after the convergent $p_n/q_n$. ## Best Approximations of the Second Kind Suppose $\theta \in \mathbb R\setminus \mathbb Q$ and we are allowed to choose integers $p$ and $q$ with $1\le q\le Q$, where $Q\in\mathbb N$ is a fixed denominator bound. The approximation error $|\theta-p/q|$ is natural, but continued fractions interact even more directly with the scaled error $|q\theta-p|$. This scaled error is the vertical distance from $q\theta$ to the nearest integer and avoids comparing fractions with different denominators by a changing factor of $q$. [definition: Best Approximation Of The Second Kind] Let $\theta\in\mathbb R\setminus\mathbb Q$. A rational number $p/q$ with $q\in\mathbb N$ and $\gcd(p,q)=1$ is a best approximation of the second kind to $\theta$ if, for every pair $(r,s)\in\mathbb Z\times\mathbb N$ with $1\le s\le q$ and $r/s\ne p/q$, we have \begin{align*} |q\theta-p| < |s\theta-r|. \end{align*} [/definition] The strict inequality says that when the denominator bound is $q$, the numerator $p$ gives the unique smallest scaled error. Some authors allow ties and then speak of weak best approximations; here the strict version is the convenient one because irrationality prevents the error from vanishing. [example: Nearest Integer For A Fixed Denominator] Fix $q\in\mathbb N$ and put $x=q\theta$. Let $n=\lfloor x\rfloor$, so \begin{align*} n\le x<n+1, \qquad x=n+\delta \end{align*} for a unique $\delta\in[0,1)$. If $0\le\delta\le 1/2$, choose $p=n$. Then for $r=n$ we have equality, while for $r\le n-1$, \begin{align*} |x-r|=x-r\ge x-(n-1)=\delta+1>\delta=|x-n|, \end{align*} and for $r\ge n+1$, \begin{align*} |x-r|=r-x\ge n+1-x=1-\delta\ge \delta=|x-n|. \end{align*} Thus $|q\theta-p|\le |q\theta-r|$ for every $r\in\mathbb Z$ in this case. If $1/2\le\delta<1$, choose $p=n+1$. Then for $r=n+1$ we have equality, while for $r\le n$, \begin{align*} |x-r|=x-r\ge x-n=\delta\ge 1-\delta=|x-(n+1)|, \end{align*} and for $r\ge n+2$, \begin{align*} |x-r|=r-x\ge n+2-x=2-\delta>1-\delta=|x-(n+1)|. \end{align*} So, once the denominator $q$ is fixed, minimising $|q\theta-r|$ only requires taking a nearest integer to $q\theta$; the real second-kind problem is deciding which denominators $q$ produce new record distances from $q\theta$ to $\mathbb Z$. [/example] The example reduces the problem to detecting record denominators. For a fixed denominator the nearest integer is automatic, but it is not obvious which denominators produce smaller values of $|q\theta-p|$ than all earlier competitors. The recurrence and determinant identity for convergents are strong enough to isolate a half-open range in which a given convergent is the record holder. [explanation: Best Approximation by Convergents] Let $\theta\in\mathbb R\setminus\mathbb Q$ have simple continued fraction convergents $p_n/q_n$. For each integer $n\geq0$, every integer pair $(p,q)$ with $q\in\mathbb N$ and $0<q<q_{n+1}$ satisfies \begin{align*} |q\theta-p|\geq |q_n\theta-p_n|. \end{align*} [/explanation] The hypotheses carry the sharp content of the statement. The denominator condition is $q<q_{n+1}$ rather than $q\le q_{n+1}$ because the endpoint $p_{n+1}/q_{n+1}$ has smaller scaled error than $p_n/q_n$; allowing $q=q_{n+1}$ would make the conclusion false. The conclusion is non-strict, so it is a record-minimality statement for the scaled error rather than the strict best-approximation definition by itself. The stricter classification is handled later in this chapter. A concrete instance is $\sqrt2$. The convergent $7/5$ is best among denominators below $12$, but at the endpoint $17/12$ the scaled error drops from $|5\sqrt2-7|$ to $|12\sqrt2-17|$. Thus the theorem describes a half-open denominator range for each convergent. It does not say that every rational approximation problem has only principal convergents as candidates; once the comparison is changed from scaled error to ordinary error, intermediate fractions can enter, and the next sections identify exactly where they sit. [example: Records For Square Root Two] For $\sqrt2=[1;2,2,2,\dots]$, the recurrence for convergents gives \begin{align*} 1,\ \frac32,\ \frac75,\ \frac{17}{12},\ \frac{41}{29},\ \frac{99}{70},\ \frac{239}{169},\ \frac{577}{408}. \end{align*} Below denominator $100$, the convergents with $q\le100$ are therefore $1/1,3/2,7/5,17/12,41/29,$ and $99/70$. We compute their scaled errors by multiplying by the conjugate. For $1/1$, \begin{align*} |\sqrt2-1|=\frac{|(\sqrt2-1)(\sqrt2+1)|}{\sqrt2+1}=\frac{|2-1|}{\sqrt2+1}=\frac1{\sqrt2+1}\approx0.4142. \end{align*} For $3/2$, \begin{align*} |2\sqrt2-3|=\frac{|(2\sqrt2-3)(2\sqrt2+3)|}{2\sqrt2+3}=\frac{|8-9|}{2\sqrt2+3}=\frac1{2\sqrt2+3}\approx0.1716. \end{align*} For $7/5$, \begin{align*} |5\sqrt2-7|=\frac{|(5\sqrt2-7)(5\sqrt2+7)|}{5\sqrt2+7}=\frac{|50-49|}{5\sqrt2+7}=\frac1{5\sqrt2+7}\approx0.0711. \end{align*} For $17/12$, \begin{align*} |12\sqrt2-17|=\frac{|(12\sqrt2-17)(12\sqrt2+17)|}{12\sqrt2+17}=\frac{|288-289|}{12\sqrt2+17}=\frac1{12\sqrt2+17}\approx0.0294. \end{align*} For $41/29$, \begin{align*} |29\sqrt2-41|=\frac{|(29\sqrt2-41)(29\sqrt2+41)|}{29\sqrt2+41}=\frac{|1682-1681|}{29\sqrt2+41}=\frac1{29\sqrt2+41}\approx0.0122. \end{align*} For $99/70$, \begin{align*} |70\sqrt2-99|=\frac{|(70\sqrt2-99)(70\sqrt2+99)|}{70\sqrt2+99}=\frac{|9800-9801|}{70\sqrt2+99}=\frac1{70\sqrt2+99}\approx0.00505. \end{align*} The denominators $\sqrt2+1$, $2\sqrt2+3$, $5\sqrt2+7$, $12\sqrt2+17$, $29\sqrt2+41$, and $70\sqrt2+99$ are strictly increasing, so these reciprocals form a strictly decreasing list of scaled errors. The next convergent after $99/70$ is $239/169$, and $169>100$; hence the best-approximation theorem for convergents says that no rational number with denominator at most $100$ can have smaller scaled error than $99/70$. [/example] ## Legendre's Criterion For Being A Convergent The preceding theorem says that convergents are optimal. A converse question is just as important in applications: if a rational approximation is extraordinarily accurate, must it have come from the continued fraction expansion? Legendre's theorem gives a sharp and usable sufficient condition. [quotetheorem:5513] [citeproof:5513] The constant $1/2$ is the useful threshold for a simple test: if the approximation error is below $1/(2q^2)$, the fraction is not accidental. It must be visible in the continued fraction expansion. Each hypothesis has a job. The reducedness hypothesis prevents the same rational number from being disguised with a larger denominator. For example, $2/2=1/1$ is not a reduced fraction. If $\theta$ is close enough to $1$ to make \begin{align*} \left|\theta-\frac22\right|<\frac{1}{2\cdot2^2}, \end{align*} the conclusion should be about the reduced denominator $1$, not about $2/2$ as a separate continued fraction convergent. The condition $q>0$ fixes a unique denominator convention: without it, the same rational could also be written as $(-p)/(-q)$, and the phrase "denominator at most $q$" would no longer define the same comparison problem. Irrationality is also essential. If $\theta=3/2$, then the reduced fraction $3/2$ satisfies the inequality with error $0$, but finite continued fractions for a rational number are not unique unless a convention is imposed: \begin{align*} \frac32=[1;2]=[1;1,1]. \end{align*} The theorem is designed for the infinite continued fraction of an irrational number, where the convergents and the next denominator $q_{n+1}$ are unambiguous. The theorem is only a sufficient condition, however, and not a necessary description of convergents. For the golden ratio $\varphi=[1;1,1,1,\dots]$, every convergent is a continued fraction convergent, but its errors satisfy \begin{align*} \left|\varphi-\frac{p_n}{q_n}\right|\sim \frac{1}{\sqrt5\,q_n^2}, \end{align*} and $1/\sqrt5>1/2$. Thus infinitely many convergents fail Legendre's inequality because the next partial quotient is small. The criterion certifies unusually strong approximations; it does not list all convergents. [example: Why Twenty Two Sevenths Appears] Using the decimal bound $3.14159265<\pi<3.14159266$, we have \begin{align*} \frac{22}{7}=3.142857142\ldots \end{align*} Hence $\pi<22/7$, and the error is bounded by \begin{align*} 0<\frac{22}{7}-\pi<3.142857143-3.14159265=0.001264493<0.001265. \end{align*} The Legendre threshold for denominator $7$ is \begin{align*} \frac{1}{2\cdot 7^2}=\frac{1}{98}=0.010204081\ldots>0.01020. \end{align*} Therefore \begin{align*} \left|\pi-\frac{22}{7}\right|<0.001265<0.01020<\frac{1}{2\cdot7^2}. \end{align*} By Legendre's criterion, the reduced fraction $22/7$ must be a convergent of the continued fraction expansion of $\pi$. Indeed the continued fraction of $\pi$ begins \begin{align*} \pi=[3;7,15,1,292,\dots], \end{align*} and the convergent determined by the first two partial quotients is \begin{align*} [3;7]=3+\frac{1}{7}=\frac{21}{7}+\frac{1}{7}=\frac{22}{7}. \end{align*} Thus the familiar approximation $22/7$ appears in the continued fraction expansion because its error is already below Legendre's forcing threshold. [/example] The same Legendre test becomes more striking when the next partial quotient is large. The approximation $22/7$ is already good enough to be certified, but $355/113$ is much better because it is followed by an unusually large jump in the continued fraction expansion. [example: Why Three Hundred Fifty Five Over One Hundred Thirteen Appears] For $355/113$, first note that the fraction is reduced: the Euclidean algorithm gives $355=3\cdot113+16$, then $113=7\cdot16+1$, and then $16=16\cdot1+0$, so $\gcd(355,113)=1$. Using $3.14159265<\pi<3.14159266$, we first check that $355/113$ lies above $\pi$: \begin{align*} \frac{355}{113}-3.14159266=\frac{355\cdot100000000-113\cdot314159266}{113\cdot100000000}=\frac{2942}{11300000000}>0. \end{align*} Thus $\pi<355/113$. The lower decimal bound gives the explicit error estimate \begin{align*} 0<\frac{355}{113}-\pi<\frac{355}{113}-3.14159265=\frac{355\cdot100000000-113\cdot314159265}{113\cdot100000000}=\frac{3055}{11300000000}. \end{align*} The Legendre threshold is \begin{align*} \frac{1}{2\cdot113^2}=\frac{1}{2\cdot12769}=\frac{1}{25538}. \end{align*} Since \begin{align*} 3055\cdot25538=78018590<11300000000, \end{align*} we have \begin{align*} \left|\pi-\frac{355}{113}\right|<\frac{3055}{11300000000}<\frac{1}{25538}=\frac{1}{2\cdot113^2}. \end{align*} By Legendre's criterion, the reduced fraction $355/113$ must be a convergent of the continued fraction expansion of $\pi$. Indeed, \begin{align*} [3;7,15,1]=3+\frac{1}{7+\frac{1}{15+\frac11}}=3+\frac{1}{7+\frac{1}{16}}=3+\frac{1}{113/16}=3+\frac{16}{113}=\frac{355}{113}. \end{align*} The next partial quotient is $292$. With $q_2=106$ and $q_3=113$, the recurrence for denominators gives \begin{align*} q_4=292q_3+q_2=292\cdot113+106=33102. \end{align*} Thus $355/113$ is followed by a jump from denominator $113$ to denominator $33102$, which explains why this convergent dominates such a long range of denominator bounds. [/example] Legendre's theorem is not a complete classification of all convergents, because many convergents fail the inequality when the next partial quotient is small. Its role is diagnostic: sufficiently strong rational approximations are certified as continued fraction data. ## Intermediate Fractions And Semiconvergents Between two consecutive convergents there are rational numbers obtained by stopping partway through the next partial quotient. These intermediate fractions matter because best approximations of the first kind need not be principal convergents but still arise from the same recurrence. [definition: Intermediate Fraction] Let $\theta=[a_0;a_1,a_2,\dots]$ be irrational, with convergents $p_n/q_n$ defined by the initial convention \begin{align*} p_{-1}=1,\qquad q_{-1}=0. \end{align*} For $n\ge0$, an admissible intermediate index is an integer $m$ satisfying $1\le m\le a_1$ when $n=0$, and $0\le m\le a_{n+1}$ when $n\ge1$. The intermediate fraction between $p_{n-1}/q_{n-1}$ and $p_n/q_n$ toward $p_{n+1}/q_{n+1}$ is \begin{align*} \frac{p_{n,m}}{q_{n,m}}:=\frac{mp_n+p_{n-1}}{mq_n+q_{n-1}}. \end{align*} [/definition] For $n\ge1$, the endpoints $m=0$ and $m=a_{n+1}$ recover $p_{n-1}/q_{n-1}$ and $p_{n+1}/q_{n+1}$ respectively. For $n=0$, the formal value $m=0$ would be $p_{-1}/q_{-1}=1/0$, so it is excluded; the first admissible value $m=1$ gives the first integer after $a_0$. The remaining values of $m$ give genuine fractions inside the interval bounded by neighbouring convergents. These are also called semiconvergents or secondary convergents. [example: Semiconvergents Before Twenty Two Sevenths] Since the continued fraction of $\pi$ begins \begin{align*} \pi=[3;7,15,1,292,\dots], \end{align*} we have $a_0=3$, $a_1=7$, and the initial convergent data are \begin{align*} p_{-1}=1,\qquad q_{-1}=0,\qquad p_0=3,\qquad q_0=1. \end{align*} For the first block of intermediate fractions, the admissible indices satisfy $1\le m\le a_1=7$. Substituting these values into the intermediate-fraction formula gives \begin{align*} \frac{p_{0,m}}{q_{0,m}}=\frac{mp_0+p_{-1}}{mq_0+q_{-1}}=\frac{3m+1}{m}=\frac{3m}{m}+\frac1m=3+\frac1m. \end{align*} Thus $m=1$ gives $(3\cdot1+1)/1=4/1$, $m=2$ gives $(3\cdot2+1)/2=7/2$, and $m=3$ gives $(3\cdot3+1)/3=10/3$. Continuing in the same formula, $m=4,5,6,7$ give \begin{align*} \frac{13}{4},\qquad \frac{16}{5},\qquad \frac{19}{6},\qquad \frac{22}{7}. \end{align*} So the whole block is \begin{align*} \frac41,\ \frac72,\ \frac{10}{3},\ \frac{13}{4},\ \frac{16}{5},\ \frac{19}{6},\ \frac{22}{7}. \end{align*} The last value agrees with the principal convergent \begin{align*} [3;7]=3+\frac17=\frac{21}{7}+\frac17=\frac{22}{7}. \end{align*} Thus the intermediate block fills the denominators $1,2,3,4,5,6,7$ on the way from the integer convergent $3/1$ to the next principal convergent $22/7$. [/example] The example shows intermediate fractions as an ordered chain rather than isolated approximations. To use them in classification results, we need the exact monotonicity and denominator formula, both of which again come from the determinant identity. [quotetheorem:5514] [citeproof:5514] Intermediate fractions should be read as the lattice points on the line segment of possible coefficient pairs between two adjacent convergent vectors. The coefficient $m$ records how many copies of the current convergent vector have been added before the next full convergent is reached. The hypotheses in the ordering theorem are boundary controls, not decoration. The restriction $n\ge1$ in the first paragraph avoids the formal denominator $q_{-1}=0$: at $n=0$ and $m=0$ the displayed fraction is $p_{-1}/q_{-1}=1/0$, so it is not a rational approximation. The endpoint values $m=0$ and $m=a_{n+1}$ are included to describe the whole ordered chain, but they are not new intermediate approximations; they recover $p_{n-1}/q_{n-1}$ and $p_{n+1}/q_{n+1}$. For instance, in the block from $3/1$ to $22/7$ for $\pi$, the endpoint $m=7$ is exactly $22/7$, while the interior values $1\le m<7$ give $4/1,7/2,\dots,19/6$. The admissible range for $m$ is also necessary. If $m>a_{n+1}$, the fraction has passed beyond the next convergent rather than lying between the two endpoints; in the same $\pi$ block, $m=8$ gives $25/8$, which is beyond $22/7$ on the ordered line of fractions. If $m<0$, the denominator $mq_n+q_{n-1}$ can become non-positive or the fraction can leave the interval in the opposite direction. Thus the theorem is only an ordering and denominator statement for a finite continued-fraction block. It does not claim that every item in the list is best for any chosen optimisation problem; the next classification result applies the second-kind comparison and explains which ordered candidates actually survive under that stricter test. ## Classification Of Best Rational Approximants The final question is structural: if a rational number is best under a denominator bound, where can it sit in the continued fraction table? The answer is that the continued fraction expansion gives all candidates: principal convergents and, depending on the exact convention, selected semiconvergents. [quotetheorem:5515] [citeproof:5515] This classification is the conceptual endpoint for the second-kind problem. Continued fractions do not merely generate good rational approximations; after the initial denominator-one exception is handled, their principal convergents are exactly the record setters for the scaled error under the strict second-kind comparison of this chapter. The hypotheses cannot be loosened without changing the conclusion. If $\theta$ is rational, a scaled error can vanish: for $\theta=3/2$, the fraction $3/2$ has $|2\theta-3|=0$, and finite continued fraction conventions must first decide whether $3/2$ is written as $[1;2]$ or $[1;1,1]$. If the competitor range is changed from $s\le q$ to $s<q$, then an endpoint tie or record at the current denominator is no longer tested in the same way, which is why some texts state a broader weak classification involving semiconvergents. If reducedness is dropped, the same rational number can be represented more than once, and equality of scaled errors can come from rewriting rather than from a new approximation. Under the reduced irrational convention used here, ties are ruled out by the concrete equations \begin{align*} |q\theta-p|=|s\theta-r| \end{align*} between distinct integer pairs. What semiconvergents provide is a warning about changing the problem: for first-kind approximation, the extra division by $q$ can allow an interior fraction $(mp_n+p_{n-1})/(mq_n+q_{n-1})$ to beat earlier ordinary errors even though the scaled-error theorem says it cannot beat the adjacent principal convergent in the second-kind sense. Thus the theorem classifies the second-kind candidates for the convention stated at the start of the chapter, while the intermediate-fraction section explains where the additional first-kind candidates come from. [example: Best Approximations To Square Root Two Below Denominator One Hundred] For $\sqrt2=[1;2,2,2,\dots]$, the recurrence \begin{align*} p_n=2p_{n-1}+p_{n-2},\qquad q_n=2q_{n-1}+q_{n-2} \end{align*} for $n\ge1$, starting from $p_0/q_0=1/1$, gives \begin{align*} \frac11,\quad \frac32,\quad \frac75,\quad \frac{17}{12},\quad \frac{41}{29},\quad \frac{99}{70},\quad \frac{239}{169}. \end{align*} Thus the convergents with denominator at most $100$ stop at $99/70$, and the next convergent has denominator $169$. We compute the scaled errors by multiplying each expression by its conjugate. For the first convergent, \begin{align*} |\sqrt2-1|=\frac{|(\sqrt2-1)(\sqrt2+1)|}{\sqrt2+1}=\frac{|2-1|}{\sqrt2+1}=\frac1{\sqrt2+1}\approx 0.4142. \end{align*} For the second, \begin{align*} |2\sqrt2-3|=\frac{|(2\sqrt2-3)(2\sqrt2+3)|}{2\sqrt2+3}=\frac{|8-9|}{2\sqrt2+3}=\frac1{2\sqrt2+3}\approx 0.1716. \end{align*} For the third, \begin{align*} |5\sqrt2-7|=\frac{|(5\sqrt2-7)(5\sqrt2+7)|}{5\sqrt2+7}=\frac{|50-49|}{5\sqrt2+7}=\frac1{5\sqrt2+7}\approx 0.0711. \end{align*} For the fourth, \begin{align*} |12\sqrt2-17|=\frac{|(12\sqrt2-17)(12\sqrt2+17)|}{12\sqrt2+17}=\frac{|288-289|}{12\sqrt2+17}=\frac1{12\sqrt2+17}\approx 0.0294. \end{align*} For the fifth, \begin{align*} |29\sqrt2-41|=\frac{|(29\sqrt2-41)(29\sqrt2+41)|}{29\sqrt2+41}=\frac{|1682-1681|}{29\sqrt2+41}=\frac1{29\sqrt2+41}\approx 0.0122. \end{align*} For the sixth, \begin{align*} |70\sqrt2-99|=\frac{|(70\sqrt2-99)(70\sqrt2+99)|}{70\sqrt2+99}=\frac{|9800-9801|}{70\sqrt2+99}=\frac1{70\sqrt2+99}\approx 0.00505. \end{align*} The denominators in these reciprocal formulas are strictly increasing, so the displayed scaled errors are strictly decreasing. Since $100<169$, every rational number with denominator at most $100$ has denominator less than the next convergent denominator $169$; by the best-approximation theorem for convergents, none of those competitors has smaller scaled error than $99/70$. Hence $99/70$ is the best approximation of the second kind to $\sqrt2$ among rationals with denominator at most $100$. [/example] This final example returns to the computational problem that opened the chapter: once the continued fraction is known, the denominator bound is handled by locating the last relevant convergent. The distinction between first-kind and second-kind approximation explains why the chapter emphasised the scaled error throughout. [remark: First Kind Versus Second Kind] Best approximations of the first kind minimise $|\theta-p/q|$ rather than $|q\theta-p|$. Since $|\theta-p/q|=|q\theta-p|/q$, increasing the denominator changes the comparison, and semiconvergents enter more naturally. The second-kind formulation is cleaner for the main theorem because the determinant identity compares the integer linear forms $q\theta-p$ directly. [/remark] This distinction between first-kind and second-kind approximation is one of the entry points from continued fractions into the broader Diophantine approximation questions of Chapter 5. Legendre's criterion gives a first test for when an unexpectedly accurate rational approximation must be a convergent, while later refinements fix constants $C>0$ and $\mu>0$ and measure how often inequalities of the form \begin{align*} \left|\theta-\frac pq\right|<\frac{C}{q^\mu} \end{align*} can occur. In that language, the size of the partial quotients controls the irrationality behaviour of $\theta$: bounded partial quotients give uniformly limited approximation quality, while large partial quotients create the exceptional approximations seen for numbers such as $\pi$. # 5. Dirichlet, Hurwitz, and Badly Approximable Numbers This chapter continues the course's development of continued fractions as a tool for Diophantine approximation. The prerequisites are the construction of continued fractions, the recurrence relations for convergents, the determinant identity, the exact error formula, and the best-approximation properties proved in the preceding chapter. The central question is: how well must an irrational number be approximated by rationals, and which numbers resist good approximation most strongly? We first prove Dirichlet's theorem in two ways, then sharpen it through [Hurwitz's theorem](/theorems/3358), and finally identify bounded partial quotients as the exact continued-fraction signature of badly approximable numbers. ## Dirichlet Approximation from Convergents Chapter 4 showed that convergents are best approximations in a precise denominator range for the scaled error $|q\theta-p|$. We now ask for a [universal approximation](/theorems/1994) guarantee: given an irrational real number $\theta$, can we always find infinitely many rationals $p/q$ whose error is on the scale $1/q^2$? [quotetheorem:1762] [citeproof:1762] This theorem is the first point where continued fractions give more than an algorithm: they guarantee a universal approximation rate and identify the rationals that cross the sharper Legendre threshold. The irrationality hypothesis is essential for the statement as written. If $\theta=a/b$ is rational in lowest terms, then $a/b$ itself has zero error, but there are only finitely many reduced rationals with denominator below any fixed bound, and the continued fraction terminates rather than producing an infinite sequence of convergents. For rational $\theta$, a nonzero approximation $p/q\ne a/b$ satisfies $|a/b-p/q|\ge 1/(bq)$, so the inequality $|a/b-p/q|<1/q^2$ cannot hold once $q>b$; this gives a concrete obstruction to the "infinitely many" conclusion. The converse in part (ii) is deliberately thresholded: an approximation below $1/(2q^2)$ is forced to be a convergent, while the broader Dirichlet scale $1/q^2$ leaves room for later sharp-constant questions. [example: Dirichlet Approximations to Square Root Two] For $\theta=\sqrt{2}=[1;2,2,2,\dots]$, the convergents begin \begin{align*} 1,\quad \frac{3}{2},\quad \frac{7}{5},\quad \frac{17}{12},\quad \frac{41}{29}. \end{align*} For the convergent $41/29$, the Pell relation is \begin{align*} 41^2-2\cdot 29^2=1681-1682=-1. \end{align*} Therefore \begin{align*} (41-29\sqrt{2})(41+29\sqrt{2})=41^2-(29\sqrt{2})^2=41^2-2\cdot 29^2=-1. \end{align*} Since $41+29\sqrt{2}>0$, taking absolute values gives \begin{align*} |29\sqrt{2}-41|=\frac{1}{41+29\sqrt{2}}. \end{align*} Dividing by $29$ then yields the exact error \begin{align*} \left|\sqrt{2}-\frac{41}{29}\right|=\frac{|29\sqrt{2}-41|}{29}=\frac{1}{29(41+29\sqrt{2})}. \end{align*} Because $41+29\sqrt{2}>29$, this implies \begin{align*} \left|\sqrt{2}-\frac{41}{29}\right|=\frac{1}{29(41+29\sqrt{2})}<\frac{1}{29\cdot 29}=\frac{1}{29^2}. \end{align*} Thus $41/29$ is a concrete Dirichlet approximation to $\sqrt{2}$, and the Pell-type identities for these convergents make the $1/q^2$ scale visible. [/example] The continued-fraction proof is short because it uses earlier structural work. There is also a proof that does not know about continued fractions, and it is useful because it shows that the exponent $2$ is already forced by a finite pigeonhole argument. ## Dirichlet Approximation from the Pigeonhole Principle Suppose we forget continued fractions and only retain the fractional parts of multiples of $\theta$. The problem becomes geometric: among many points in the unit interval, two must fall close together, and their difference produces a good rational approximation. [quotetheorem:5516] [citeproof:5516] The finite version is often the most useful form in elementary number theory: it gives control over the denominator before it gives a sequence. The hypothesis $\theta\in\mathbb R$ is deliberately broad here, because the finite pigeonhole estimate remains true for rational and irrational numbers. The infinite consequence, however, needs irrationality for the same reason as before: a rational number has only finitely many exceptionally close nonzero approximations at this scale. The denominator bound $q\le N$ is also part of the content, not a technical decoration. It says that a good approximation appears before a prescribed search limit, but it does not identify the best denominator below $N$, does not guarantee uniqueness, and does not say that the denominator found for one $N$ remains optimal when $N$ is enlarged. Continued fractions improve the same theorem by identifying the best choices of $q$ rather than merely proving that some choice exists. [remark: Strict and Non-Strict Constants] The pigeonhole argument naturally gives $|q\theta-p|\le 1/N$, while the convergent argument gives a strict inequality for irrational $\theta$. This distinction has no effect on the qualitative statement that infinitely many $p/q$ satisfy an error bound of order $1/q^2$, but it matters when studying sharp constants. [/remark] After the two proofs of Dirichlet's theorem, the next question is whether the constant $1$ in Dirichlet's inequality can be improved uniformly. Dirichlet's constant is not sharp: among consecutive convergents, the recurrences force at least some errors to be smaller than the coarse bound $1/q^2$. At the same time, looking only for isolated good convergents is not enough to describe resistance to approximation by all rationals, because a number can have occasional excellent convergents while still resisting most denominators. Hurwitz's theorem gives the sharp universal improvement, while the following section introduces the stronger all-rationals lower bound that defines bad approximation. ## Hurwitz Approximation and the Golden Ratio Dirichlet's theorem guarantees infinitely many approximations with error below $1/q^2$. The sharper question is whether every irrational number admits infinitely many approximations with \begin{align*} \left|\theta-\frac{p}{q}\right|<\frac{C}{q^2} \end{align*} for a universal constant $C<1$. [quotetheorem:5517] [citeproof:5517] Hurwitz's theorem is a refinement of Dirichlet's theorem, not a replacement for the theory of best approximations. The irrationality hypothesis is again necessary: rational numbers have terminating continued fractions, so there is no infinite tail of convergents to which the argument can be applied, and nonzero rational approximations eventually have error bounded below by a multiple of $1/q$. The theorem also does not say that every rational approximation is this good, or even that every convergent is this good; it guarantees infinitely many successful approximations distributed through the convergent sequence. Its sharpness statement is global: the golden ratio shows that any constant below $1/\sqrt{5}$ fails for at least one irrational number, not merely that a particular sequence has a suggestive limiting value. [example: The Golden Ratio as the Hardest Case] Let $\varphi=(1+\sqrt{5})/2=[1;1,1,1,\dots]$, and define the Fibonacci numbers by $F_0=0$, $F_1=1$, and $F_{k+2}=F_{k+1}+F_k$. Since every partial quotient after $a_0$ is $1$, the continued-fraction recurrence gives \begin{align*} \frac{p_n}{q_n}=\frac{F_{n+2}}{F_{n+1}}. \end{align*} Thus the convergents begin \begin{align*} \frac{1}{1},\quad \frac{2}{1},\quad \frac{3}{2},\quad \frac{5}{3},\quad \frac{8}{5},\quad \dots. \end{align*} We compute the scaled error for these convergents. Put $\psi=(1-\sqrt{5})/2$, so $\psi=-1/\varphi$ and $\psi-\varphi=-\sqrt{5}$. Binet's formula is \begin{align*} F_k=\frac{\varphi^k-\psi^k}{\sqrt{5}}. \end{align*} Using this formula first for $F_{n+1}$ and then for $F_{n+2}$, \begin{align*} \varphi F_{n+1}-F_{n+2} = \varphi\frac{\varphi^{n+1}-\psi^{n+1}}{\sqrt{5}} -\frac{\varphi^{n+2}-\psi^{n+2}}{\sqrt{5}}. \end{align*} Combining the numerators gives \begin{align*} \varphi F_{n+1}-F_{n+2} = \frac{\varphi^{n+2}-\varphi\psi^{n+1}-\varphi^{n+2}+\psi^{n+2}}{\sqrt{5}}. \end{align*} The two $\varphi^{n+2}$ terms cancel, and factoring out $\psi^{n+1}$ gives \begin{align*} \varphi F_{n+1}-F_{n+2} = \frac{\psi^{n+1}(\psi-\varphi)}{\sqrt{5}}. \end{align*} Since $\psi-\varphi=-\sqrt{5}$, this becomes \begin{align*} \varphi F_{n+1}-F_{n+2}=-\psi^{n+1}. \end{align*} Therefore \begin{align*} \left|\varphi-\frac{F_{n+2}}{F_{n+1}}\right| = \frac{|\varphi F_{n+1}-F_{n+2}|}{F_{n+1}}. \end{align*} Substituting the identity just proved gives \begin{align*} \left|\varphi-\frac{F_{n+2}}{F_{n+1}}\right| = \frac{|\psi|^{n+1}}{F_{n+1}}. \end{align*} Because $|\psi|=1/\varphi$, this is \begin{align*} \left|\varphi-\frac{F_{n+2}}{F_{n+1}}\right| = \frac{1}{\varphi^{n+1}F_{n+1}}. \end{align*} Now $q_n=F_{n+1}$, so multiplying by $q_n^2$ gives \begin{align*} q_n^2\left|\varphi-\frac{p_n}{q_n}\right| = F_{n+1}^2\left|\varphi-\frac{F_{n+2}}{F_{n+1}}\right|. \end{align*} Using the preceding error formula, \begin{align*} q_n^2\left|\varphi-\frac{p_n}{q_n}\right| = \frac{F_{n+1}}{\varphi^{n+1}}. \end{align*} Applying Binet's formula once more, \begin{align*} \frac{F_{n+1}}{\varphi^{n+1}} = \frac{\varphi^{n+1}-\psi^{n+1}}{\sqrt{5}\,\varphi^{n+1}}. \end{align*} Dividing both terms in the numerator by $\varphi^{n+1}$ gives \begin{align*} \frac{F_{n+1}}{\varphi^{n+1}} = \frac{1-(\psi/\varphi)^{n+1}}{\sqrt{5}}. \end{align*} Since $\psi/\varphi=-1/\varphi^2$ and $|-1/\varphi^2|<1$, the term $(\psi/\varphi)^{n+1}$ tends to $0$. Hence \begin{align*} q_n^2\left|\varphi-\frac{p_n}{q_n}\right|\longrightarrow \frac{1}{\sqrt{5}}. \end{align*} Thus the golden ratio reaches the Hurwitz threshold along its convergents: its continued fraction has no large partial quotients, so the usual mechanism that produces much smaller scaled errors never appears. [/example] The golden ratio fixes the sharp universal threshold because its continued fraction never gives the approximation process a large partial quotient. Replacing the repeated $1$ by repeated $2$ already changes the limiting constant, and $\sqrt{2}$ is the standard comparison. [example: Square Root Two is Easier than the Golden Ratio] The number $\sqrt{2}=[1;2,2,2,\dots]$ has all later partial quotients equal to $2$. Let $p_n/q_n$ be its convergents, indexed by $p_0/q_0=1/1$ and $p_1/q_1=3/2$. For $n\ge 1$, the continued-fraction recurrence gives $p_{n+1}=2p_n+p_{n-1}$ and $q_{n+1}=2q_n+q_{n-1}$. Set $\alpha=1+\sqrt{2}$ and $\beta=1-\sqrt{2}$. Since $\alpha$ and $\beta$ are the roots of $x^2-2x-1=0$, both satisfy $x^{n+1}=2x^n+x^{n-1}$ for $n\ge 1$. The denominator sequence with $q_0=1$ and $q_1=2$ is therefore \begin{align*} q_n=\frac{\alpha^{n+1}-\beta^{n+1}}{2\sqrt{2}}. \end{align*} The numerator sequence with $p_0=1$ and $p_1=3$ is \begin{align*} p_n=\frac{\alpha^{n+1}+\beta^{n+1}}{2}. \end{align*} These formulas have the stated initial values and satisfy the same recurrence, so they agree with the convergent numerators and denominators. Now compute the error. Substituting the two closed forms gives \begin{align*} \sqrt{2}\,q_n-p_n = \sqrt{2}\cdot \frac{\alpha^{n+1}-\beta^{n+1}}{2\sqrt{2}} - \frac{\alpha^{n+1}+\beta^{n+1}}{2}. \end{align*} The first factor of $\sqrt{2}$ cancels, so \begin{align*} \sqrt{2}\,q_n-p_n = \frac{\alpha^{n+1}-\beta^{n+1}}{2} - \frac{\alpha^{n+1}+\beta^{n+1}}{2}. \end{align*} Combining the two fractions gives \begin{align*} \sqrt{2}\,q_n-p_n = \frac{\alpha^{n+1}-\beta^{n+1}-\alpha^{n+1}-\beta^{n+1}}{2} = -\beta^{n+1}. \end{align*} Since $\beta=1-\sqrt{2}$ and $|\beta|=\sqrt{2}-1=1/(1+\sqrt{2})=1/\alpha$, we get \begin{align*} \left|\sqrt{2}-\frac{p_n}{q_n}\right| = \frac{|\sqrt{2}\,q_n-p_n|}{q_n} = \frac{|\beta|^{n+1}}{q_n} = \frac{1}{\alpha^{n+1}q_n}. \end{align*} Multiplying by $q_n^2$ gives \begin{align*} q_n^2\left|\sqrt{2}-\frac{p_n}{q_n}\right| = \frac{q_n}{\alpha^{n+1}}. \end{align*} Using the closed form for $q_n$, \begin{align*} \frac{q_n}{\alpha^{n+1}} = \frac{\alpha^{n+1}-\beta^{n+1}}{2\sqrt{2}\,\alpha^{n+1}} = \frac{1-(\beta/\alpha)^{n+1}}{2\sqrt{2}}. \end{align*} Also, \begin{align*} \frac{\beta}{\alpha} = \frac{1-\sqrt{2}}{1+\sqrt{2}} = \frac{(1-\sqrt{2})^2}{1-2} = -(3-2\sqrt{2}). \end{align*} Thus $|\beta/\alpha|=3-2\sqrt{2}<1$, so $(\beta/\alpha)^{n+1}\to 0$. Hence \begin{align*} q_n^2\left|\sqrt{2}-\frac{p_n}{q_n}\right| \longrightarrow \frac{1}{2\sqrt{2}}. \end{align*} Finally, $1/(2\sqrt{2})<1/\sqrt{5}$ because $\sqrt{5}<2\sqrt{2}$, equivalently $5<8$. Thus $\sqrt{2}$ is easier to approximate than the golden ratio on the Hurwitz scale: its repeated partial quotient $2$ makes the limiting scaled error smaller than the golden-ratio threshold. [/example] The examples show that the size of the partial quotients governs approximation quality. Large partial quotients create unusually good approximations, while uniformly small partial quotients prevent the error from becoming too small too often. ## Bounded Partial Quotients and Bad Approximation We now reverse the viewpoint. Instead of asking how good the approximations must be, we ask which irrational numbers resist approximation by all rationals at the scale $1/q^2$. [definition: Badly Approximable Number] An irrational number $\theta\in\mathbb R\setminus\mathbb Q$ is badly approximable if there exists a constant $c(\theta)>0$ such that for all $p\in\mathbb Z$ and all $q\in\mathbb N$, \begin{align*} \left|\theta-\frac{p}{q}\right|\ge \frac{c(\theta)}{q^2}. \end{align*} [/definition] This definition does not say that $\theta$ has poor rational approximations in an absolute sense: Dirichlet still gives infinitely many approximations of order $1/q^2$. It says that the hidden constant in front of $1/q^2$ cannot be driven arbitrarily close to $0$. [example: Golden Ratio is Badly Approximable] Let $\varphi=(1+\sqrt{5})/2=[1;1,1,1,\dots]$. Every partial quotient after $a_0$ is equal to $1$, so the bounded-partial-quotient theorem below will imply that $\varphi$ is badly approximable. The same resistance is visible along the convergents: if $F_0=0$, $F_1=1$, and $F_{k+2}=F_{k+1}+F_k$, then \begin{align*} \frac{p_n}{q_n}=\frac{F_{n+2}}{F_{n+1}}. \end{align*} Put $\psi=(1-\sqrt{5})/2$. Since $\psi=-1/\varphi$, Binet's formula gives \begin{align*} F_k=\frac{\varphi^k-\psi^k}{\sqrt{5}}. \end{align*} Using this formula for $F_{n+1}$ and $F_{n+2}$, \begin{align*} \varphi F_{n+1}-F_{n+2}=\varphi\frac{\varphi^{n+1}-\psi^{n+1}}{\sqrt{5}}-\frac{\varphi^{n+2}-\psi^{n+2}}{\sqrt{5}}. \end{align*} Combining the two fractions gives \begin{align*} \varphi F_{n+1}-F_{n+2}=\frac{\varphi^{n+2}-\varphi\psi^{n+1}-\varphi^{n+2}+\psi^{n+2}}{\sqrt{5}}. \end{align*} The $\varphi^{n+2}$ terms cancel, so \begin{align*} \varphi F_{n+1}-F_{n+2}=\frac{-\varphi\psi^{n+1}+\psi^{n+2}}{\sqrt{5}}. \end{align*} Factoring out $\psi^{n+1}$ gives \begin{align*} \varphi F_{n+1}-F_{n+2}=\frac{\psi^{n+1}(\psi-\varphi)}{\sqrt{5}}. \end{align*} Because $\psi-\varphi=-\sqrt{5}$, this becomes \begin{align*} \varphi F_{n+1}-F_{n+2}=-\psi^{n+1}. \end{align*} Therefore \begin{align*} \left|\varphi-\frac{F_{n+2}}{F_{n+1}}\right|=\frac{|\varphi F_{n+1}-F_{n+2}|}{F_{n+1}}. \end{align*} Substituting the identity just proved gives \begin{align*} \left|\varphi-\frac{F_{n+2}}{F_{n+1}}\right|=\frac{|\psi|^{n+1}}{F_{n+1}}. \end{align*} Since $|\psi|=1/\varphi$, \begin{align*} \left|\varphi-\frac{F_{n+2}}{F_{n+1}}\right|=\frac{1}{\varphi^{n+1}F_{n+1}}. \end{align*} Now $q_n=F_{n+1}$, so multiplying by $q_n^2$ gives \begin{align*} q_n^2\left|\varphi-\frac{p_n}{q_n}\right|=F_{n+1}^2\left|\varphi-\frac{F_{n+2}}{F_{n+1}}\right|. \end{align*} Using the preceding error formula, \begin{align*} q_n^2\left|\varphi-\frac{p_n}{q_n}\right|=\frac{F_{n+1}}{\varphi^{n+1}}. \end{align*} Applying Binet's formula again, \begin{align*} \frac{F_{n+1}}{\varphi^{n+1}}=\frac{\varphi^{n+1}-\psi^{n+1}}{\sqrt{5}\,\varphi^{n+1}}. \end{align*} Dividing both terms in the numerator by $\varphi^{n+1}$ gives \begin{align*} \frac{F_{n+1}}{\varphi^{n+1}}=\frac{1-(\psi/\varphi)^{n+1}}{\sqrt{5}}. \end{align*} Since $\psi/\varphi=-1/\varphi^2$, we have $|(\psi/\varphi)^{n+1}|\le 1/\varphi^2$ for every $n\ge 0$. Hence \begin{align*} q_n^2\left|\varphi-\frac{p_n}{q_n}\right|\ge \frac{1-1/\varphi^2}{\sqrt{5}}>0. \end{align*} The Fibonacci convergents therefore never make the scaled error $q_n^2|\varphi-p_n/q_n|$ approach $0$, which is the concrete continued-fraction signal behind the bad approximability of the golden ratio. [/example] To connect the definition with continued fractions, we need to translate a global lower bound against all rationals into information about the continued-fraction digits. The obstruction is that badly approximable numbers are defined by every fraction $p/q$, while partial quotients only directly control the special convergents. A criterion is needed that bridges those two descriptions without losing the uniform lower bound. [quotetheorem:5518] [citeproof:5518] This theorem is one of the main reasons continued fractions are powerful in Diophantine approximation. A metric-looking property involving all rationals $p/q$ becomes the simple symbolic condition that the entries in the continued fraction expansion stay bounded. Both directions need their hypotheses. Irrationality is built into the definition because rational numbers have exact rational representations and therefore cannot satisfy a positive lower bound for all $p/q$ when $p/q=\theta$. Boundedness is also essential: $e=[2;1,2,1,1,4,1,1,6,\dots]$ gives a concrete unbounded-partial-quotient example, and the convergents following the large entries make $q_n^2|e-p_n/q_n|$ arbitrarily small. The phrase "for all $p\in\mathbb Z$ and all $q\in\mathbb N$" is doing real work in the definition. Controlling only the convergents would not by itself give a badly approximable number, because the definition asks for a uniform lower barrier against every possible rational denominator. The proof passes from convergents to all reduced rationals using Legendre's criterion: any rational that violates the proposed lower bound strongly enough would have to be a convergent, so the convergent estimates rule it out. This is why the theorem is stronger than the informal statement "the convergents are not too good". It says that no non-convergent rational can evade the same lower bound. The result does not provide a universal lower constant shared by all badly approximable numbers, since the constant depends on the bound for the particular continued fraction. [example: Comparing Square Root Two, e, and an Unbounded Case] For $\sqrt{2}=[1;2,2,2,\dots]$, every partial quotient after the initial term is equal to $2$. Thus, for all $n\ge 1$, \begin{align*} a_n=2\le 2, \end{align*} so the partial quotients are bounded. By the *badly approximable numbers and bounded partial quotients* criterion, $\sqrt{2}$ is badly approximable. For \begin{align*} e=[2;1,2,1,1,4,1,1,6,\dots], \end{align*} the displayed pattern contains the subsequence \begin{align*} a_2=2,\qquad a_5=4,\qquad a_8=6,\qquad \dots, \end{align*} that is, \begin{align*} a_{3m-1}=2m\qquad (m\ge 1). \end{align*} Since $2m\to\infty$, the partial quotients of $e$ are unbounded. The same criterion therefore shows that $e$ is not badly approximable. Finally let \begin{align*} \theta=[0;1,2,3,4,5,\dots], \end{align*} and write $p_n/q_n$ for its convergents. Here the partial quotients satisfy $a_{n+1}=n+1$, so they are unbounded. The convergent denominator recurrence gives \begin{align*} q_{n+1}=a_{n+1}q_n+q_{n-1}. \end{align*} Since $q_{n-1}\ge 0$, this implies \begin{align*} q_{n+1}\ge a_{n+1}q_n. \end{align*} Using the standard convergent error estimate, \begin{align*} \left|\theta-\frac{p_n}{q_n}\right|<\frac{1}{q_nq_{n+1}}, \end{align*} we get \begin{align*} q_n^2\left|\theta-\frac{p_n}{q_n}\right| < \frac{q_n^2}{q_nq_{n+1}} = \frac{q_n}{q_{n+1}} \le \frac{q_n}{a_{n+1}q_n} = \frac{1}{a_{n+1}} = \frac{1}{n+1}. \end{align*} Because $1/(n+1)\to 0$, the scaled errors along these convergents can be made arbitrarily small. This is the visible mechanism behind the failure of bad approximability when the partial quotients are unbounded. [/example] This comparison separates three behaviours that can otherwise look similar from decimal approximations alone. Quadratic irrationals can be resistant because their expansions repeat, special transcendental numbers such as $e$ may have structured but unbounded entries, and artificial examples can make the failure of bad approximability visible by construction. [remark: Badly Approximable Does Not Mean Rare in the Course Sense] Badly approximable numbers form a thin set from the viewpoint of [Lebesgue measure](/page/Lebesgue%20Measure), but they are arithmetically prominent because quadratic irrationals have eventually periodic continued fractions and hence bounded partial quotients. Thus $\sqrt{2}$ and $\varphi$ both belong to this class, while $e$ does not. [/remark] The chapter has now linked three levels of approximation. Dirichlet gives a universal $1/q^2$ upper scale, Hurwitz sharpens the universal constant to $1/\sqrt{5}$, and badly approximable numbers are exactly those whose continued fractions prevent constants smaller and smaller than a positive threshold. A convenient way to package this information is through the Markov constant \begin{align*} M(\theta)=\liminf_{q\to\infty}\; q\,\|q\theta\|_{\mathbb R/\mathbb Z}, \end{align*} where $\|x\|_{\mathbb R/\mathbb Z}$ denotes distance from $x$ to the nearest integer. The number $\theta$ is badly approximable exactly when $M(\theta)>0$, and Hurwitz's theorem says that every irrational has infinitely many $q$ with $q\,\|q\theta\|_{\mathbb R/\mathbb Z}<1/\sqrt{5}$. For quadratic irrationals this constant is tied to the eventually periodic continued fractions studied in Chapter 6 and to the Pell equations of Chapter 8. Later courses use the same constants to compare different irrational numbers more finely. # 6. Periodic Continued Fractions and Quadratic Irrationals The previous chapters showed that continued fractions give a systematic supply of good rational approximations, and that unusually good approximations are controlled by the partial quotients. This chapter studies the opposite direction: what arithmetic information is encoded when the partial quotients repeat? The answer is one of the central structural results of the course: periodicity is exactly the continued-fraction signature of quadratic irrationality. We first separate eventual repetition from repetition starting at the beginning, then attach a fractional linear transformation to one full period. This connects continued fractions with quadratic equations. The final section gives the sharper criterion for purely periodic expansions, expressed through reduced quadratic irrationals and their conjugates. ## Eventually Periodic Continued Fractions The guiding question is: if the same block of partial quotients appears forever, why should the value satisfy a quadratic equation? The key point is that one period acts on the tail by a Mobius transformation, so a periodic tail is a fixed point of a rational fractional [linear map](/page/Linear%20Map). [definition: Eventually Periodic Continued Fraction] Let $\theta \in \mathbb R \setminus \mathbb Q$ have simple continued fraction expansion \begin{align*} \theta = [a_0; a_1, a_2, \dots]. \end{align*} The expansion is eventually periodic if there exist integers $N \ge 0$ and $r \ge 1$ such that \begin{align*} a_{n+r} = a_n \quad \text{for all } n \ge N. \end{align*} [/definition] Thus an eventually periodic continued fraction has a non-repeating preperiod followed by a repeating block. We write $[a_0; a_1, \dots, a_{N-1}, \overline{b_1, \dots, b_r}]$ for the expansion whose tail repeats $b_1,\dots,b_r$ forever. The case with no preperiod behaves better under conjugation, so we need a separate name for repetitions that begin at the integer part itself. [definition: Purely Periodic Continued Fraction] Let $\theta \in \mathbb R \setminus \mathbb Q$ have simple continued fraction expansion \begin{align*} \theta = [a_0; a_1, a_2, \dots]. \end{align*} The expansion is purely periodic if there exists $r \ge 1$ such that \begin{align*} a_{n+r} = a_n \quad \text{for all } n \ge 0. \end{align*} [/definition] Pure periodicity is stronger because the repetition begins with the integer part. Since simple continued fractions have $a_n \in \mathbb N$ for $n \ge 1$ but allow $a_0 \in \mathbb Z$, this condition is quite restrictive for real numbers in the usual normalisation. [example: Two Forms Of The Square Root Of Two] Let \begin{align*} x=[\overline{2}]=2+\frac{1}{2+\frac{1}{2+\cdots}}. \end{align*} The tail after the first $2$ is again the same infinite continued fraction, so \begin{align*} x=2+\frac{1}{x}. \end{align*} Since $x>0$, multiplying both sides by $x$ gives \begin{align*} x^2=2x+1. \end{align*} Equivalently, \begin{align*} x^2-2x-1=0. \end{align*} The [quadratic formula](/theorems/1301) gives \begin{align*} x=\frac{2\pm\sqrt{(-2)^2-4(1)(-1)}}{2}. \end{align*} The discriminant is \begin{align*} (-2)^2-4(1)(-1)=4+4=8, \end{align*} so \begin{align*} x=\frac{2\pm\sqrt{8}}{2}=1\pm\sqrt{2}. \end{align*} Because $x=[\overline{2}]>2$, the relevant root is \begin{align*} [\overline{2}]=1+\sqrt{2}. \end{align*} The more familiar expansion of $\sqrt{2}$ has one initial partial quotient before the repetition begins. Using the value just found, \begin{align*} [1;\overline{2}]=1+\frac{1}{[\overline{2}]}. \end{align*} Thus \begin{align*} [1;\overline{2}]=1+\frac{1}{1+\sqrt{2}}. \end{align*} To rationalise the denominator, multiply the fraction by $\frac{\sqrt{2}-1}{\sqrt{2}-1}$: \begin{align*} 1+\frac{1}{1+\sqrt{2}}=1+\frac{\sqrt{2}-1}{(1+\sqrt{2})(\sqrt{2}-1)}. \end{align*} The denominator expands as \begin{align*} (1+\sqrt{2})(\sqrt{2}-1)=\sqrt{2}-1+2-\sqrt{2}=1. \end{align*} Therefore \begin{align*} 1+\frac{1}{1+\sqrt{2}}=1+\sqrt{2}-1=\sqrt{2}. \end{align*} So \begin{align*} \sqrt{2}=[1;\overline{2}], \end{align*} while the purely periodic representative with the same repeating block is $1+\sqrt{2}=[\overline{2}]$. [/example] The example shows that a repeating block can be converted into an equation for its value. To prove this in general, we need a notation for the operation of appending a variable tail after one finite block. [definition: Mobius Transformation Attached To A Block] Let $b_1,\dots,b_r \in \mathbb N$, and let $\mathcal D_{b_1,\dots,b_r}\subseteq \mathbb R$ be the set of real $x$ for which the finite continued fraction $[b_1;b_2,\dots,b_r,x]$ is defined. The Mobius transformation attached to the block $(b_1,\dots,b_r)$ is the map \begin{align*} T: \mathcal D_{b_1,\dots,b_r} \longrightarrow \mathbb R, \qquad x \longmapsto [b_1; b_2, \dots, b_r, x], \end{align*} [/definition] The preceding definition turns a repeating continued-fraction block into a single algebraic operation. Its contribution is that the infinite repetition is replaced by the fixed-point equation $T(x)=x$. This equation has integer coefficients once the continuant formula is used, so it explains why an eventually periodic expansion should give a quadratic irrational. The following theorem is the full Lagrange equivalence; the paragraphs after it separate the two directions so the proof idea remains visible. [quotetheorem:1763] [citeproof:1763] The theorem is a classification result, so its hypotheses matter. Eventual periodicity is needed because the repeating part of the expansion is the data being classified, while a finite non-repeating initial segment is allowed before that repetition begins. Irrationality is also needed. For example, \begin{align*} \frac{3}{2} = [1;2]. \end{align*} This is a finite continued fraction, so it should not be treated as a quadratic irrational merely because it admits endpoint conventions. At the other boundary, an irrational continued fraction such as $[0;1,2,3,4,\dots]$ has no repeating block, so it lies outside the periodic side of the classification. The practical message is that periodicity is not a numerical decoration: it is exactly the continued-fraction signature of quadratic irrationality. The next subsection refines this by asking when the repetition starts immediately. ## Lagrange's Theorem The reverse implication asks why the complete quotients of a quadratic irrational must eventually repeat. The proof uses the complete quotient formula from Chapter 2, together with bounds on the conjugate root. [definition: Quadratic Irrational] A real number $\theta$ is a quadratic irrational if $\theta \notin \mathbb Q$ and there exist $A,B,C \in \mathbb Z$ with $A \ne 0$ such that \begin{align*} A\theta^2 + B\theta + C = 0. \end{align*} [/definition] Equivalently, \begin{align*} \theta = \frac{u+v\sqrt{d}}{w} \end{align*} for integers $u,v,w,d$ with $v w \ne 0$, $d > 1$, and $d$ not a square. This equivalent form is often the most convenient way to track conjugates. The general Lagrange equivalence quoted above gives the precise test: quadratic irrationality and eventual periodicity are the same phenomenon. Each hypothesis has a visible role. If $\theta \in \mathbb Q$, the simple continued fraction terminates, so the infinite eventual-periodicity statement is the wrong object: for example, \begin{align*} \frac{7}{5}=[1;2,2] \end{align*} is finite rather than periodic in the sense of the theorem. By contrast, an infinite non-eventually-periodic expansion has no finite period from which to build the fixed quadratic equation of the preceding section. The theorem also has a limitation: it promises eventual repetition, not repetition from the first partial quotient. The difference between $[1;\overline{2}]$ and $[\overline{2}]$ shows why a separate conjugate condition is needed to decide whether there is a preperiod. In computations, the period is found by iterating complete quotients until a previous one reappears. The square-root special case receives its own concrete version in the next chapter. [example: Golden Ratio As A Reduced Quadratic Irrational] Let \begin{align*} \varphi=\frac{1+\sqrt{5}}{2}. \end{align*} We first verify the identity that produces the repeating continued fraction. Since \begin{align*} \frac{1}{\varphi}=\frac{1}{(1+\sqrt{5})/2}, \end{align*} we have \begin{align*} \frac{1}{\varphi}=\frac{2}{1+\sqrt{5}}. \end{align*} Rationalising the denominator gives \begin{align*} \frac{2}{1+\sqrt{5}}\cdot \frac{\sqrt{5}-1}{\sqrt{5}-1} =\frac{2(\sqrt{5}-1)}{(1+\sqrt{5})(\sqrt{5}-1)}. \end{align*} The denominator expands as \begin{align*} (1+\sqrt{5})(\sqrt{5}-1)=\sqrt{5}-1+5-\sqrt{5}=4, \end{align*} so \begin{align*} \frac{1}{\varphi}=\frac{2(\sqrt{5}-1)}{4}=\frac{\sqrt{5}-1}{2}. \end{align*} Therefore \begin{align*} 1+\frac{1}{\varphi}=1+\frac{\sqrt{5}-1}{2}. \end{align*} Writing $1=2/2$, this becomes \begin{align*} 1+\frac{\sqrt{5}-1}{2}=\frac{2+\sqrt{5}-1}{2}=\frac{1+\sqrt{5}}{2}=\varphi. \end{align*} Thus \begin{align*} \varphi=1+\frac{1}{\varphi}. \end{align*} Substituting the same expression for $\varphi$ in the denominator repeatedly gives \begin{align*} \varphi=1+\frac{1}{1+\frac{1}{1+\frac{1}{\cdots}}}, \end{align*} so \begin{align*} \varphi=[\overline{1}]. \end{align*} To identify the conjugate, clear the radical from the definition of $\varphi$. From \begin{align*} 2\varphi=1+\sqrt{5}, \end{align*} we get \begin{align*} 2\varphi-1=\sqrt{5}. \end{align*} Squaring both sides gives \begin{align*} (2\varphi-1)^2=5. \end{align*} Expanding the square, \begin{align*} 4\varphi^2-4\varphi+1=5. \end{align*} Subtracting $5$ and dividing by $4$ gives \begin{align*} \varphi^2-\varphi-1=0. \end{align*} The two roots of $x^2-x-1$ are \begin{align*} \frac{1+\sqrt{5}}{2}\quad\text{and}\quad \frac{1-\sqrt{5}}{2}, \end{align*} so the conjugate is \begin{align*} \varphi'=\frac{1-\sqrt{5}}{2}. \end{align*} Because $2<\sqrt{5}<3$, subtracting from $1$ gives \begin{align*} -2<1-\sqrt{5}<-1. \end{align*} Dividing by $2$ gives \begin{align*} -1<\frac{1-\sqrt{5}}{2}<-\frac{1}{2}<0. \end{align*} Also $\varphi=(1+\sqrt{5})/2>1$. Hence $\varphi$ lies in the reduced range used in the next section: its value is greater than $1$, its conjugate lies in $(-1,0)$, and its continued fraction begins immediately with the repeating block $1$. [/example] [Lagrange's theorem](/theorems/841) does not say when the period starts immediately. For that, we need to use the second root of the same quadratic equation. ## Reduced Quadratic Irrationals And Conjugates The next question is: among all quadratic irrationals, which ones have a purely periodic expansion? The answer depends not only on the number itself but also on its algebraic conjugate. A first warning comes from $\sqrt{2}$ and $1+\sqrt{2}$: the former has expansion $[1;\overline{2}]$, while the latter has expansion $[\overline{2}]$, even though they lie in the same quadratic field and differ by an integer. [definition: Algebraic Conjugate Of A Quadratic Irrational] Let $\theta$ be a quadratic irrational with [minimal polynomial](/page/Minimal%20Polynomial) \begin{align*} A x^2 + Bx + C \in \mathbb Z[x]. \end{align*} The algebraic conjugate of $\theta$, denoted $\theta'$, is the other real root of this polynomial. [/definition] The conjugate records the same quadratic equation viewed from the other root. Continued-fraction transformations act on both roots, and the sign and size of the conjugate determine whether the algorithm returns immediately to the starting point. This motivates isolating the range of quadratic irrationals whose chosen root and conjugate root sit on the two sides required by the continued-fraction map. [definition: Reduced Quadratic Irrational] A quadratic irrational $\theta$ is reduced if \begin{align*} \theta > 1, \qquad -1 < \theta' < 0. \end{align*} [/definition] This condition is asymmetric in the two roots: the chosen root is greater than $1$, while its conjugate lies in the interval $(-1,0)$. It is exactly adapted to simple continued fractions, because applying \begin{align*} x \longmapsto \frac{1}{x-a} \end{align*} to complete quotients preserves the relevant interval structure. [example: Reduced Form For The Golden Ratio] Let \begin{align*} \varphi = \frac{1+\sqrt{5}}{2}. \end{align*} Its conjugate is obtained by changing $\sqrt{5}$ to $-\sqrt{5}$, so \begin{align*} \varphi'=\frac{1-\sqrt{5}}{2}. \end{align*} We verify the two inequalities in the reduced condition. Since \begin{align*} \sqrt{5}>1, \end{align*} we have \begin{align*} 1+\sqrt{5}>2, \end{align*} and dividing by $2$ gives \begin{align*} \varphi=\frac{1+\sqrt{5}}{2}>1. \end{align*} Also \begin{align*} 2^2=4<5<9=3^2, \end{align*} so, because square root is increasing on positive real numbers, \begin{align*} 2<\sqrt{5}<3. \end{align*} Subtracting from $1$ reverses the order: \begin{align*} -2<1-\sqrt{5}<-1. \end{align*} Dividing by $2$ gives \begin{align*} -1<\frac{1-\sqrt{5}}{2}<-\frac{1}{2}<0. \end{align*} Thus \begin{align*} \varphi>1 \qquad\text{and}\qquad -1<\varphi'<0, \end{align*} so $\varphi$ is reduced. Its continued fraction expansion is $[\overline{1}]$, making it the simplest purely periodic example. [/example] The reduced condition is not just a convenient normal form. It is designed to rule out the two ways a quadratic irrational can have an initial transient part: the value may start in the wrong integer range, or its conjugate may lie on the wrong inverse branch. This raises the precise converse problem: after imposing exactly those two inequalities, is there still any hidden obstruction that could delay the repeating block? The point of the criterion is to show that no further normalization is needed; the continued fraction should be periodic from its first partial quotient. [quotetheorem:1764] [citeproof:1764] This result explains why $[\overline{2}]$ gives $1+\sqrt{2}$, not $\sqrt{2}$. The two inequalities in the reduced condition rule out different failures. The condition $\theta>1$ is needed because a purely periodic simple continued fraction begins with a positive integer partial quotient, so its value is greater than $1$. For instance, the number \begin{align*} \frac{1+\sqrt{2}}{3} \end{align*} has conjugate \begin{align*} \frac{1-\sqrt{2}}{3}\in(-1,0), \end{align*} but is less than $1$, and its expansion begins with integer part $0$ rather than purely periodically. The two inequalities in the definition rule out two different failures: the chosen number may be too small, or its conjugate may lie outside the required interval. For instance, $\sqrt{2}>1$, but its conjugate is $-\sqrt{2}<-1$, so $\sqrt{2}$ needs the initial non-repeating partial quotient in $[1;\overline{2}]$. The number $1+\sqrt{2}$ satisfies both conditions because its conjugate is \begin{align*} 1-\sqrt{2}\in(-1,0). \end{align*} The theorem does not say that every quadratic irrational is purely periodic in its original form; it says that the reduced representatives are the ones whose repetition starts at once. For a general quadratic irrational, the earlier Lagrange theorem still guarantees eventual repetition, while the reduced condition identifies the special starting positions with no preperiod. ## Computing Periods In Practice The theoretical statements become useful only when paired with an explicit algorithm. For a square root or a quadratic irrational written in radicals, the period is obtained by iterating the complete quotient formula and watching the integer parameters repeat. [example: Period Of The Square Root Of Two] Starting from $\sqrt{2}$, its integer part is $1$ because \begin{align*} 1^2=1<2<4=2^2, \end{align*} so $1<\sqrt{2}<2$. The first complete quotient after removing the integer part is \begin{align*} \frac{1}{\sqrt{2}-1}. \end{align*} Rationalising the denominator, \begin{align*} \frac{1}{\sqrt{2}-1}=\frac{1}{\sqrt{2}-1}\cdot \frac{\sqrt{2}+1}{\sqrt{2}+1}. \end{align*} The numerator is $\sqrt{2}+1$, and the denominator expands as \begin{align*} (\sqrt{2}-1)(\sqrt{2}+1)=2+\sqrt{2}-\sqrt{2}-1=1. \end{align*} Therefore \begin{align*} \frac{1}{\sqrt{2}-1}=\sqrt{2}+1. \end{align*} Since $1<\sqrt{2}<2$, adding $1$ gives \begin{align*} 2<\sqrt{2}+1<3, \end{align*} so the next integer part is $2$. Subtracting this integer part gives \begin{align*} (\sqrt{2}+1)-2=\sqrt{2}-1. \end{align*} Taking the reciprocal returns the same complete quotient: \begin{align*} \frac{1}{(\sqrt{2}+1)-2}=\frac{1}{\sqrt{2}-1}=\sqrt{2}+1. \end{align*} Thus after the initial partial quotient $1$, the partial quotient $2$ repeats forever, and \begin{align*} \sqrt{2}=[1;\overline{2}]. \end{align*} The corresponding purely periodic value is the repeated complete quotient itself: \begin{align*} 1+\sqrt{2}=[\overline{2}]. \end{align*} This separates the non-reduced starting value $\sqrt{2}$ from its reduced companion $1+\sqrt{2}$, where the same period begins immediately. [/example] A slightly richer computation shows the same mechanism with a different reduced representative. The previous example began with a non-reduced number and then uncovered its reduced companion after one continued-fraction step. The next example starts directly from the reduced representative in a different quadratic field, so the computation has no transient stage: the defining quadratic identity already gives the full period. [example: Reduced Representative For A Quadratic Field] In the field $\mathbb Q(\sqrt{5})$, consider \begin{align*} \varphi=\frac{1+\sqrt{5}}{2}. \end{align*} We first check that this representative is reduced. Since \begin{align*} 2^2=4<5<9=3^2, \end{align*} and square root is increasing on positive real numbers, we have \begin{align*} 2<\sqrt{5}<3. \end{align*} Adding $1$ gives \begin{align*} 3<1+\sqrt{5}<4, \end{align*} and dividing by $2$ gives \begin{align*} \frac{3}{2}<\frac{1+\sqrt{5}}{2}<2. \end{align*} Thus $\varphi>1$. The conjugate is obtained by changing $\sqrt{5}$ to $-\sqrt{5}$: \begin{align*} \varphi'=\frac{1-\sqrt{5}}{2}. \end{align*} From \begin{align*} 2<\sqrt{5}<3, \end{align*} subtracting from $1$ reverses the inequalities: \begin{align*} -2<1-\sqrt{5}<-1. \end{align*} Dividing by $2$ gives \begin{align*} -1<\frac{1-\sqrt{5}}{2}<-\frac{1}{2}<0. \end{align*} Therefore \begin{align*} \varphi>1 \end{align*} and \begin{align*} -1<\varphi'<0, \end{align*} so $\varphi$ is reduced. Now compute the identity that gives the period. From the definition of $\varphi$, \begin{align*} \frac{1}{\varphi}=\frac{1}{(1+\sqrt{5})/2}. \end{align*} Dividing by $(1+\sqrt{5})/2$ is the same as multiplying by $2/(1+\sqrt{5})$, so \begin{align*} \frac{1}{\varphi}=\frac{2}{1+\sqrt{5}}. \end{align*} Rationalising the denominator gives \begin{align*} \frac{2}{1+\sqrt{5}}=\frac{2}{1+\sqrt{5}}\cdot\frac{\sqrt{5}-1}{\sqrt{5}-1}. \end{align*} Thus \begin{align*} \frac{2}{1+\sqrt{5}}=\frac{2(\sqrt{5}-1)}{(1+\sqrt{5})(\sqrt{5}-1)}. \end{align*} The denominator expands as \begin{align*} (1+\sqrt{5})(\sqrt{5}-1)=\sqrt{5}-1+5-\sqrt{5}. \end{align*} Cancelling $\sqrt{5}-\sqrt{5}$ gives \begin{align*} \sqrt{5}-1+5-\sqrt{5}=4. \end{align*} Hence \begin{align*} \frac{1}{\varphi}=\frac{2(\sqrt{5}-1)}{4}. \end{align*} Cancelling a factor of $2$ gives \begin{align*} \frac{1}{\varphi}=\frac{\sqrt{5}-1}{2}. \end{align*} Therefore \begin{align*} 1+\frac{1}{\varphi}=1+\frac{\sqrt{5}-1}{2}. \end{align*} Writing $1=2/2$, we get \begin{align*} 1+\frac{\sqrt{5}-1}{2}=\frac{2}{2}+\frac{\sqrt{5}-1}{2}. \end{align*} Combining the numerators gives \begin{align*} \frac{2}{2}+\frac{\sqrt{5}-1}{2}=\frac{1+\sqrt{5}}{2}. \end{align*} Thus \begin{align*} 1+\frac{1}{\varphi}=\varphi. \end{align*} Substituting the identity $\varphi=1+1/\varphi$ into the denominator repeatedly gives \begin{align*} \varphi=1+\frac{1}{1+\frac{1}{1+\frac{1}{\cdots}}}. \end{align*} So the continued fraction has a single repeating partial quotient: \begin{align*} \varphi=[\overline{1}]. \end{align*} This example starts already at a reduced complete quotient, so there is no initial preperiod before the repeating block begins. [/example] The chapter's conclusion is therefore twofold. Repetition of partial quotients is not a numerical accident: it is the fixed-point behaviour of an integral Mobius transformation. The precise location of the conjugate root decides whether the repetition begins immediately or only after a finite preperiod. This is the same bridge that reappears in Chapter 10's dynamical and matrix viewpoints: arithmetic properties of a quadratic field are reflected in the orbit of a fractional linear transformation with integer coefficients. # 7. Square Root Expansions This chapter turns the general theory of periodic continued fractions into a concrete algorithm for square roots. Chapter 6 tied periodicity to quadratic irrationality; here we specialise to numbers of the form $\sqrt{D}$ with $D \in \mathbb N$ nonsquare and extract the integer recurrences that make the expansion computable by hand. The main questions are: how do we generate the partial quotients without numerical approximation, why does the expansion repeat, and what symmetry does the period have? ## Complete Quotients for Square Roots The continued fraction algorithm repeatedly replaces a real number by the reciprocal of its fractional part. For $\sqrt{D}$ this process stays inside a small family of quadratic surds, and the point of the next definition is to name the integer parameters that describe each complete quotient. [definition: Square Root Recurrence Data] Let $D \in \mathbb N$ be nonsquare and set $a_0 = \lfloor \sqrt{D} \rfloor$. Define integer sequences $(m_n)_{n \ge 0}$, $(d_n)_{n \ge 0}$, and $(a_n)_{n \ge 0}$ by $m_0=0$, $d_0=1$, $a_0=\lfloor \sqrt{D}\rfloor$, and, for $n \ge 0$, \begin{align*} m_{n+1} = d_n a_n - m_n. \end{align*} \begin{align*} d_{n+1} = \frac{D - m_{n+1}^2}{d_n}. \end{align*} \begin{align*} a_{n+1} = \left\lfloor \frac{a_0 + m_{n+1}}{d_{n+1}} \right\rfloor . \end{align*} [/definition] These formulas would be unhelpful if they merely produced integers with no connection to the original continued fraction algorithm. The next theorem is needed to identify the recurrence data with the complete quotients, which proves that the computed $a_n$ are the actual partial quotients of $\sqrt{D}$. [quotetheorem:5519] [citeproof:5519] This theorem reduces the expansion of $\sqrt{D}$ to integer arithmetic, but it also marks exactly where the nonsquare hypothesis enters. If $D=a_0^2$ is a square, then $\sqrt{D}=a_0$ is already an integer, the continued fraction terminates, and the step $1/(\alpha_0-a_0)$ is not defined. Thus the recurrence is not a disguised algorithm for all square roots: it is an algorithm for irrational square roots, where the fractional part never vanishes. The theorem also does not by itself prove periodicity. It says that every complete quotient has the controlled shape $(\sqrt{D}+m_n)/d_n$ and that the divisibility relation is preserved, but a separate finite-state argument is still needed to show that only finitely many admissible pairs can occur. Without those bounds, the recurrence could in principle wander through infinitely many integer pairs while still producing correct complete quotients. [example: Expansion of Square Root of Seven] For $D=7$ we have $a_0=\lfloor \sqrt{7}\rfloor=2$, since $2^2=4<7<9=3^2$. Starting from $(m_0,d_0,a_0)=(0,1,2)$, the square-root recurrence gives \begin{align*} m_1=d_0a_0-m_0=1\cdot 2-0=2. \end{align*} \begin{align*} d_1=\frac{7-m_1^2}{d_0}=\frac{7-2^2}{1}=3. \end{align*} \begin{align*} a_1=\left\lfloor \frac{a_0+m_1}{d_1}\right\rfloor=\left\lfloor \frac{2+2}{3}\right\rfloor=1. \end{align*} Thus $(m_1,d_1,a_1)=(2,3,1)$. The next step is \begin{align*} m_2=d_1a_1-m_1=3\cdot 1-2=1. \end{align*} \begin{align*} d_2=\frac{7-m_2^2}{d_1}=\frac{7-1^2}{3}=2. \end{align*} \begin{align*} a_2=\left\lfloor \frac{a_0+m_2}{d_2}\right\rfloor=\left\lfloor \frac{2+1}{2}\right\rfloor=1. \end{align*} So $(m_2,d_2,a_2)=(1,2,1)$. Continuing, \begin{align*} m_3=d_2a_2-m_2=2\cdot 1-1=1. \end{align*} \begin{align*} d_3=\frac{7-m_3^2}{d_2}=\frac{7-1^2}{2}=3. \end{align*} \begin{align*} a_3=\left\lfloor \frac{a_0+m_3}{d_3}\right\rfloor=\left\lfloor \frac{2+1}{3}\right\rfloor=1. \end{align*} Hence $(m_3,d_3,a_3)=(1,3,1)$. The next triple is obtained from \begin{align*} m_4=d_3a_3-m_3=3\cdot 1-1=2. \end{align*} \begin{align*} d_4=\frac{7-m_4^2}{d_3}=\frac{7-2^2}{3}=1. \end{align*} \begin{align*} a_4=\left\lfloor \frac{a_0+m_4}{d_4}\right\rfloor=\left\lfloor \frac{2+2}{1}\right\rfloor=4. \end{align*} Thus $(m_4,d_4,a_4)=(2,1,4)$. One more step checks the return point: \begin{align*} m_5=d_4a_4-m_4=1\cdot 4-2=2. \end{align*} \begin{align*} d_5=\frac{7-m_5^2}{d_4}=\frac{7-2^2}{1}=3. \end{align*} Therefore $(m_5,d_5)=(2,3)=(m_1,d_1)$. Since the recurrence is deterministic, the same pairs and partial quotients now repeat, so \begin{align*} \sqrt{7}=[2;\overline{1,1,1,4}]. \end{align*} The computation stays entirely in integer arithmetic, and the closing partial quotient is $4=2a_0$. [/example] ## Periodicity of Square Root Expansions The recurrence produces a sequence of integer pairs, but a periodic continued fraction requires more than eventual repetition: the repeat must occur at the correct point in the complete quotient cycle. The next theorem is the square-root form of [Lagrange's theorem](/theorems/782) and is the main structural result of this chapter. [quotetheorem:4498] [citeproof:4498] The theorem gives existence of a period, but it is deliberately only an existence statement. The nonsquare hypothesis is again essential: for $D=9$, the expansion is just $[3]$, so there is no nonzero repeating block generated by reciprocal fractional parts. For nonsquare $D$, the finite-state argument proves eventual repetition and the special square-root recurrence removes the preperiod, but it does not yet say which partial quotient closes the cycle or whether the entries inside the period have any symmetry. This limitation matters computationally. A period such as $[4;\overline{1,2,5}]$ is periodic as a continued fraction pattern, but it has not been shown to be the period of a square root, and the last term is not $2\cdot 4$. The next results identify the additional structure that distinguishes square-root periods from arbitrary periodic continued fractions. [example: Expansion of Square Root of Twenty Three] For $D=23$, we have $4^2=16<23<25=5^2$, so $a_0=\lfloor \sqrt{23}\rfloor=4$. Starting from $(m_0,d_0,a_0)=(0,1,4)$, the square-root recurrence gives \begin{align*} m_1=d_0a_0-m_0=1\cdot 4-0=4. \end{align*} \begin{align*} d_1=\frac{23-m_1^2}{d_0}=\frac{23-4^2}{1}=\frac{23-16}{1}=7. \end{align*} \begin{align*} a_1=\left\lfloor \frac{a_0+m_1}{d_1}\right\rfloor =\left\lfloor \frac{4+4}{7}\right\rfloor =\left\lfloor \frac{8}{7}\right\rfloor=1. \end{align*} Thus $(m_1,d_1,a_1)=(4,7,1)$. The next step is \begin{align*} m_2=d_1a_1-m_1=7\cdot 1-4=3. \end{align*} \begin{align*} d_2=\frac{23-m_2^2}{d_1}=\frac{23-3^2}{7}=\frac{23-9}{7}=\frac{14}{7}=2. \end{align*} \begin{align*} a_2=\left\lfloor \frac{a_0+m_2}{d_2}\right\rfloor =\left\lfloor \frac{4+3}{2}\right\rfloor =\left\lfloor \frac{7}{2}\right\rfloor=3. \end{align*} So $(m_2,d_2,a_2)=(3,2,3)$. Continuing, \begin{align*} m_3=d_2a_2-m_2=2\cdot 3-3=3. \end{align*} \begin{align*} d_3=\frac{23-m_3^2}{d_2}=\frac{23-3^2}{2}=\frac{23-9}{2}=\frac{14}{2}=7. \end{align*} \begin{align*} a_3=\left\lfloor \frac{a_0+m_3}{d_3}\right\rfloor =\left\lfloor \frac{4+3}{7}\right\rfloor =\left\lfloor 1\right\rfloor=1. \end{align*} Hence $(m_3,d_3,a_3)=(3,7,1)$. The next triple is \begin{align*} m_4=d_3a_3-m_3=7\cdot 1-3=4. \end{align*} \begin{align*} d_4=\frac{23-m_4^2}{d_3}=\frac{23-4^2}{7}=\frac{23-16}{7}=\frac{7}{7}=1. \end{align*} \begin{align*} a_4=\left\lfloor \frac{a_0+m_4}{d_4}\right\rfloor =\left\lfloor \frac{4+4}{1}\right\rfloor =\left\lfloor 8\right\rfloor=8. \end{align*} Thus $(m_4,d_4,a_4)=(4,1,8)$. One more step checks the return point: \begin{align*} m_5=d_4a_4-m_4=1\cdot 8-4=4. \end{align*} \begin{align*} d_5=\frac{23-m_5^2}{d_4}=\frac{23-4^2}{1}=23-16=7. \end{align*} Therefore $(m_5,d_5)=(4,7)=(m_1,d_1)$. Since the recurrence is deterministic, the same pairs and partial quotients now repeat, so \begin{align*} \sqrt{23}=[4;\overline{1,3,1,8}]. \end{align*} The preterminal entries $1,3,1$ form a palindrome, and the final partial quotient is $8=2\cdot 4=2a_0$. [/example] ## Symmetry and the Last Partial Quotient After the period has been found, two patterns recur in every example: the last partial quotient is twice the integer part of $\sqrt{D}$, and the preceding partial quotients form a palindrome. The reason is that the recurrence can be run backwards once the complete quotient returns to the special denominator $1$. [explanation: Closing Check for Square-Root Periods] For a nonsquare $D\in\mathbb N$, write $a_0=\lfloor\sqrt{D}\rfloor$. In the square-root recurrence, the period closes when the recurrence returns to the state with denominator $1$ and numerator parameter $a_0$. At that closing step, the displayed partial quotient is $2a_0$. [/explanation] This is best read as a computational checkpoint for the square-root recurrence. A general periodic continued fraction such as $[2;\overline{1,3}]$ has a last displayed period entry $3$, not $2a_0=4$, because it is not produced by the square-root recurrence with the denominator-one closing state. The checkpoint also controls only the final entry of the period; it does not yet explain why the earlier entries should mirror each other. This is the remaining structural question. Once the terminal pair is fixed, the same recurrence can be read backwards as well as forwards, and that reversibility is what forces the preterminal part of the period to be palindromic. The next theorem turns the endpoint information into a statement about every earlier partial quotient in the period. [quotetheorem:5520] [citeproof:5520] The symmetry is not only a visual pattern; it is a useful check on hand computations. Its hypotheses are restrictive: arbitrary periodic continued fractions need not end in $2a_0$, and even when a finite block happens to contain a palindrome, that alone does not make the value a square root. For instance, $[2;\overline{1,3}]$ is periodic, but its displayed period does not have the square-root terminal form $[2;\overline{\cdots,4}]$, so the theorem gives no symmetry conclusion. The result is therefore best read as a diagnostic for the square-root algorithm, not as a general theorem about periodic continued fractions. A missing denominator simplification or an incorrect floor usually breaks the palindrome before the last term appears, and that failure signals that the recurrence data no longer match the complete quotients. [example: Expansion of Square Root of Sixty One] For $D=61$, we have $7^2=49<61<64=8^2$, so $a_0=\lfloor \sqrt{61}\rfloor=7$. Starting from $(m_0,d_0,a_0)=(0,1,7)$, the first step of the square-root recurrence gives \begin{align*} m_1=d_0a_0-m_0=1\cdot 7-0=7. \end{align*} \begin{align*} d_1=\frac{61-m_1^2}{d_0}=\frac{61-7^2}{1}=\frac{61-49}{1}=12. \end{align*} \begin{align*} a_1=\left\lfloor \frac{a_0+m_1}{d_1}\right\rfloor=\left\lfloor \frac{7+7}{12}\right\rfloor=\left\lfloor \frac{14}{12}\right\rfloor=1. \end{align*} Thus $(m_1,d_1,a_1)=(7,12,1)$. Continuing, \begin{align*} m_2=d_1a_1-m_1=12\cdot 1-7=5. \end{align*} \begin{align*} d_2=\frac{61-m_2^2}{d_1}=\frac{61-5^2}{12}=\frac{61-25}{12}=\frac{36}{12}=3. \end{align*} \begin{align*} a_2=\left\lfloor \frac{7+5}{3}\right\rfloor=\left\lfloor \frac{12}{3}\right\rfloor=4. \end{align*} So $(m_2,d_2,a_2)=(5,3,4)$. The next recurrence steps are \begin{align*} m_3=d_2a_2-m_2=3\cdot 4-5=7. \end{align*} \begin{align*} d_3=\frac{61-m_3^2}{d_2}=\frac{61-7^2}{3}=\frac{61-49}{3}=\frac{12}{3}=4. \end{align*} \begin{align*} a_3=\left\lfloor \frac{7+7}{4}\right\rfloor=\left\lfloor \frac{14}{4}\right\rfloor=3. \end{align*} Hence $(m_3,d_3,a_3)=(7,4,3)$, and \begin{align*} m_4=d_3a_3-m_3=4\cdot 3-7=5. \end{align*} \begin{align*} d_4=\frac{61-m_4^2}{d_3}=\frac{61-5^2}{4}=\frac{61-25}{4}=\frac{36}{4}=9. \end{align*} \begin{align*} a_4=\left\lfloor \frac{7+5}{9}\right\rfloor=\left\lfloor \frac{12}{9}\right\rfloor=1. \end{align*} Thus $(m_4,d_4,a_4)=(5,9,1)$. Continuing through the middle of the period, \begin{align*} m_5=d_4a_4-m_4=9\cdot 1-5=4. \end{align*} \begin{align*} d_5=\frac{61-m_5^2}{d_4}=\frac{61-4^2}{9}=\frac{61-16}{9}=\frac{45}{9}=5. \end{align*} \begin{align*} a_5=\left\lfloor \frac{7+4}{5}\right\rfloor=\left\lfloor \frac{11}{5}\right\rfloor=2. \end{align*} So $(m_5,d_5,a_5)=(4,5,2)$, and \begin{align*} m_6=d_5a_5-m_5=5\cdot 2-4=6. \end{align*} \begin{align*} d_6=\frac{61-m_6^2}{d_5}=\frac{61-6^2}{5}=\frac{61-36}{5}=\frac{25}{5}=5. \end{align*} \begin{align*} a_6=\left\lfloor \frac{7+6}{5}\right\rfloor=\left\lfloor \frac{13}{5}\right\rfloor=2. \end{align*} Thus $(m_6,d_6,a_6)=(6,5,2)$. The recurrence then gives \begin{align*} m_7=d_6a_6-m_6=5\cdot 2-6=4. \end{align*} \begin{align*} d_7=\frac{61-m_7^2}{d_6}=\frac{61-4^2}{5}=\frac{61-16}{5}=\frac{45}{5}=9. \end{align*} \begin{align*} a_7=\left\lfloor \frac{7+4}{9}\right\rfloor=\left\lfloor \frac{11}{9}\right\rfloor=1. \end{align*} So $(m_7,d_7,a_7)=(4,9,1)$. Next, \begin{align*} m_8=d_7a_7-m_7=9\cdot 1-4=5. \end{align*} \begin{align*} d_8=\frac{61-m_8^2}{d_7}=\frac{61-5^2}{9}=\frac{61-25}{9}=\frac{36}{9}=4. \end{align*} \begin{align*} a_8=\left\lfloor \frac{7+5}{4}\right\rfloor=\left\lfloor \frac{12}{4}\right\rfloor=3. \end{align*} Hence $(m_8,d_8,a_8)=(5,4,3)$, and \begin{align*} m_9=d_8a_8-m_8=4\cdot 3-5=7. \end{align*} \begin{align*} d_9=\frac{61-m_9^2}{d_8}=\frac{61-7^2}{4}=\frac{61-49}{4}=\frac{12}{4}=3. \end{align*} \begin{align*} a_9=\left\lfloor \frac{7+7}{3}\right\rfloor=\left\lfloor \frac{14}{3}\right\rfloor=4. \end{align*} Thus $(m_9,d_9,a_9)=(7,3,4)$. The next step is \begin{align*} m_{10}=d_9a_9-m_9=3\cdot 4-7=5. \end{align*} \begin{align*} d_{10}=\frac{61-m_{10}^2}{d_9}=\frac{61-5^2}{3}=\frac{61-25}{3}=\frac{36}{3}=12. \end{align*} \begin{align*} a_{10}=\left\lfloor \frac{7+5}{12}\right\rfloor=\left\lfloor \frac{12}{12}\right\rfloor=1. \end{align*} So $(m_{10},d_{10},a_{10})=(5,12,1)$. The terminal step is \begin{align*} m_{11}=d_{10}a_{10}-m_{10}=12\cdot 1-5=7. \end{align*} \begin{align*} d_{11}=\frac{61-m_{11}^2}{d_{10}}=\frac{61-7^2}{12}=\frac{61-49}{12}=\frac{12}{12}=1. \end{align*} \begin{align*} a_{11}=\left\lfloor \frac{7+7}{1}\right\rfloor=\left\lfloor 14\right\rfloor=14. \end{align*} Hence $(m_{11},d_{11},a_{11})=(7,1,14)$. One more step checks that the cycle has returned to the first recurring pair: \begin{align*} m_{12}=d_{11}a_{11}-m_{11}=1\cdot 14-7=7. \end{align*} \begin{align*} d_{12}=\frac{61-m_{12}^2}{d_{11}}=\frac{61-7^2}{1}=\frac{61-49}{1}=12. \end{align*} Therefore $(m_{12},d_{12})=(7,12)=(m_1,d_1)$. Since the recurrence is deterministic, the partial quotients now repeat, so \begin{align*} \sqrt{61}=[7;\overline{1,4,3,1,2,2,1,3,4,1,14}]. \end{align*} The entries before the final term $14=2\cdot 7=2a_0$ are $1,4,3,1,2,2,1,3,4,1$, which read the same forward and backward; the long period shows why the integer recurrence is more reliable than estimating $\sqrt{61}$ by decimals. [/example] ## Using the Recurrence Reliably The square-root recurrence is an algorithm, but its reliability comes from the structural theorems above. In practice, every computation should track the pair $(m_n,d_n)$, the divisibility $d_n \mid D-m_n^2$, and the expected terminal condition $(m_n,d_n)=(a_0,1)$. [remark: Computational Checks] For $D$ nonsquare, the following checks should hold during a correct hand computation: $0 \le m_n < \sqrt{D}$, $d_n>0$, $d_n \mid D-m_n^2$, and \begin{align*} a_n = \left\lfloor \frac{a_0+m_n}{d_n}\right\rfloor . \end{align*} When the period closes, the last partial quotient is $2a_0$ and the previous entries are symmetric. [/remark] These checks are especially important for the connection with Pell equations in Chapter 8. The convergents at or near the end of the period encode solutions to $x^2-Dy^2=\pm 1$, so the arithmetic of $(m_n,d_n,a_n)$ becomes a bridge between continued fractions and Diophantine equations. # 8. Pell's Equation from Convergents This chapter turns the theory of periodic continued fractions into an algorithm for solving Pell equations. The guiding question is: when does a rational approximation of the form \begin{align*} \frac{p}{q} \end{align*} to $\sqrt{D}$ become so good that the integer \begin{align*} p^2-Dq^2 \end{align*} is forced to be $1$ or $-1$? Chapter 7 showed that $\sqrt{D}$ has a periodic continued fraction expansion when $D$ is not a square; here the period length and the convergents control the integer expression $p_n^2-Dq_n^2$. ## The Positive Pell Equation and a Multiplicative Value The equation \begin{align*} x^2-Dy^2=1 \end{align*} asks for integer points on a hyperbola. We first name the equation whose solutions will be tracked by continued fractions. [definition: Pell Equation] Let $D \in \mathbb N$ be not a square. The positive Pell equation associated to $D$ is \begin{align*} x^2-Dy^2=1, \end{align*} with unknowns $x,y \in \mathbb Z$. [/definition] The next definition is needed to keep the integer quantity $x^2-Dy^2$ visible during computations. The restriction that $D$ is not a square is essential for the course: if $D$ were square, the equation would factor over $\mathbb Z$ and would not exhibit the same continued-fraction behaviour. For nonsquare $D$, this quantity is useful because it is compatible with multiplying expressions of the form $x+y\sqrt D$. [definition: Pell Value] Let $D \in \mathbb N$ be not a square. The Pell value of an integer pair $(x,y)$ is \begin{align*} P_D(x,y)=x^2-Dy^2. \end{align*} [/definition] Thus solutions of the positive Pell equation are precisely integer pairs with Pell value $1$. This notation would be of limited use if it only renamed the equation. The useful question is whether the value-one condition is stable under multiplying the corresponding expressions $x+y\sqrt D$. Without such compatibility, multiplying two Pell solutions could leave the equation behind, and the notation would not produce new integer points from known ones. [explanation: Multiplicativity of the Pell Value] For integers $a,b,c,d$ one has \begin{align*} (a+b\sqrt{D})(c+d\sqrt{D})=(ac+Dbd)+(ad+bc)\sqrt{D}. \end{align*} The Pell value of the product pair is multiplicative: \begin{align*} (ac+Dbd)^2-D(ad+bc)^2=(a^2-Db^2)(c^2-Dd^2). \end{align*} [/explanation] The integer-coefficient hypothesis matters: the product pair still has integer coordinates because both original pairs have integer coordinates, while allowing arbitrary real coefficients would no longer encode integer solutions of Pell's equation. For instance, the expression $\sqrt{3}+1\sqrt{2}$ has formal value \begin{align*} (\sqrt{3})^2-2\cdot 1^2=1, \end{align*} but it does not have the form $x+y\sqrt{2}$ with $x,y \in \mathbb Z$. It therefore does not represent an integer point $(x,y)$ on the Pell hyperbola. The identity above also does not say that every value-one pair has positive coordinates, nor does it classify all such pairs; it only gives the closure property needed to multiply known solutions. This closure is what makes the continued-fraction output reusable rather than a collection of isolated coincidences. The same expression also explains why the equation should be connected to approximating $\sqrt{D}$. If \begin{align*} x^2-Dy^2=\pm 1, \end{align*} then \begin{align*} \left|\frac{x}{y}-\sqrt{D}\right|=\frac{1}{y^2\left|x/y+\sqrt{D}\right|}, \end{align*} so the quotient of the two integer coordinates is a very accurate approximation when $y$ is large. The best approximation theory for convergents is therefore the natural tool. [example: The First Pell Solutions for D Equals Two] For $D=2$, the continued fraction expansion is $\sqrt{2}=[1;\overline{2}]$, and its first convergents are \begin{align*} 1,\quad \frac{3}{2},\quad \frac{7}{5},\quad \frac{17}{12}. \end{align*} For the convergent $3/2$, the Pell value calculation is \begin{align*} 3^2-2\cdot 2^2=9-2\cdot 4=9-8=1. \end{align*} Thus $3+2\sqrt{2}$ corresponds to a value-one solution. Squaring this expression gives \begin{align*} (3+2\sqrt{2})^2=3^2+2\cdot 3\cdot 2\sqrt{2}+(2\sqrt{2})^2. \end{align*} Since $(2\sqrt{2})^2=4\cdot 2=8$, this becomes \begin{align*} (3+2\sqrt{2})^2=9+12\sqrt{2}+8=17+12\sqrt{2}. \end{align*} The corresponding Pell value calculation is \begin{align*} 17^2-2\cdot 12^2=289-2\cdot 144=289-288=1. \end{align*} So the value-one expression $3+2\sqrt{2}$ produces the next displayed positive solution $17+12\sqrt{2}$ by ordinary multiplication and collection of the rational and $\sqrt{2}$ parts. [/example] This example suggests two facts that will be proved in the rest of the chapter. First, the successful convergents are not accidental: they occur at positions determined by the period of the continued fraction for $\sqrt{D}$. Second, the multiplication law for Pell values turns one solution into many, so the later solutions should be organised by powers of a first positive solution expression. The next theorem isolates the first of these facts by computing $p_n^2-Dq_n^2$ at each period endpoint. ## Convergents Give Pell Solutions The next problem is to identify exactly which convergents of $\sqrt{D}$ solve a Pell equation. The continued fraction period contains enough arithmetic information to compute $p_n^2-Dq_n^2$ at the end of each period. [quotetheorem:4499] [citeproof:4499] The theorem translates a periodicity statement into an integer equation, and the nonsquare hypothesis is essential because the periodic expansion of $\sqrt{D}$ is the mechanism producing the endpoint formula. If $D=4$, then $\sqrt{D}=2$ is already rational, so there is no periodic block with a minimal length $L$ to insert into the formula. Minimality of the period is also part of the data: for $\sqrt{2}=[1;\overline{2}]$ the minimal period has $L=1$, and replacing it by the nonminimal repeated block $[1;\overline{2,2}]$ would hide the genuine first endpoint $p_0/q_0=1$, where $p_0^2-2q_0^2=-1$. That nonminimal period would make the first visible endpoint $p_1/q_1=3/2$, so the parity information needed for the negative Pell equation would be wrong. The index condition is equally restrictive: for $D=13$ with $L=5$ the intermediate convergent $p_1/q_1=4/1$ has \begin{align*} 4^2-13\cdot 1^2=3, \end{align*} so a general convergent need not solve either Pell equation. It also separates the positive and negative Pell equations: the sign at the first period endpoint is positive when $L$ is even and negative when $L$ is odd. This is the precise point where the continued-fraction period becomes a solvability test rather than only an approximation device. [example: Solving the Positive Pell Equation for D Equals Thirteen] For $D=13$, the continued fraction expansion is \begin{align*} \sqrt{13}=[3;\overline{1,1,1,1,6}], \end{align*} so the minimal period length is $L=5$. Since $L$ is odd, the Pell-convergent theorem above gives value $-1$ at the first period endpoint. The endpoint convergent is \begin{align*} [3;1,1,1,1]=3+\frac{1}{1+\frac{1}{1+\frac{1}{1+1}}}=3+\frac{1}{1+\frac{1}{1+\frac{1}{2}}}=3+\frac{1}{1+\frac{1}{\frac{3}{2}}}=3+\frac{1}{1+\frac{2}{3}}=3+\frac{1}{\frac{5}{3}}=3+\frac{3}{5}=\frac{18}{5}. \end{align*} Its Pell value is \begin{align*} 18^2-13\cdot 5^2=324-13\cdot 25=324-325=-1. \end{align*} Thus $18+5\sqrt{13}$ corresponds to a value-minus-one solution. Squaring it gives \begin{align*} (18+5\sqrt{13})^2=18^2+2\cdot 18\cdot 5\sqrt{13}+(5\sqrt{13})^2. \end{align*} Since $(5\sqrt{13})^2=25\cdot 13=325$, this becomes \begin{align*} (18+5\sqrt{13})^2=324+180\sqrt{13}+325=649+180\sqrt{13}. \end{align*} The corresponding Pell value calculation is \begin{align*} 649^2-13\cdot 180^2=421201-13\cdot 32400=421201-421200=1. \end{align*} Thus the positive Pell solution first appears after two periods rather than after one, and the smallest positive solution is $649+180\sqrt{13}$. [/example] The example shows why the positive equation may require two periods rather than one. What still needs explanation is why the continued-fraction process cannot miss the positive Pell equation entirely. Even when the first period endpoint has value $-1$, the period structure should still force some positive value-one integer point to appear. [quotetheorem:4500] [citeproof:4500] Existence is stronger than it first appears: the proof does not search randomly among integer pairs. The nonsquare hypothesis again matters, since for square $D$ the expression $x^2-Dy^2$ factors over $\mathbb Z$ and the conclusion with $x,y \in \mathbb N$ may fail. For example, when $D=4$ the equation becomes \begin{align*} (x-2y)(x+2y)=1, \end{align*} so the only integer solutions have $y=0$ and hence give no solution in $\mathbb N^2$. The theorem does not identify the smallest positive solution in the statement; it only guarantees a constructive source of at least one positive solution from one or two periods. This distinction is important computationally, because the same period data must still be inspected to decide whether the first positive solution occurs after one period or after two. [example: Why D Equals Sixty-One Has a Large First Solution] For $D=61$, the continued fraction expansion is \begin{align*} \sqrt{61}=[7;\overline{1,4,3,1,2,2,1,3,4,1,14}], \end{align*} so the minimal period length is $L=11$. Since $L$ is odd, the Pell-convergent theorem above gives value $-1$ at the first period endpoint, and a positive value-one solution expression is obtained by squaring that endpoint. Using the convergent recurrence \begin{align*} p_n=a_np_{n-1}+p_{n-2},\qquad q_n=a_nq_{n-1}+q_{n-2}, \end{align*} with $p_{-2}=0$, $p_{-1}=1$, $q_{-2}=1$, and $q_{-1}=0$, the first-period endpoint is \begin{align*} \frac{p_{10}}{q_{10}}=\frac{29718}{3805}. \end{align*} Its Pell value is obtained by multiplying out the two integer terms: \begin{align*} 29718^2=883159524. \end{align*} Also, \begin{align*} 3805^2=14478025. \end{align*} Therefore \begin{align*} 61\cdot 3805^2=61\cdot 14478025=883159525. \end{align*} Hence \begin{align*} 29718^2-61\cdot 3805^2=883159524-883159525=-1. \end{align*} Thus $29718+3805\sqrt{61}$ corresponds to value $-1$. Squaring this expression gives \begin{align*} (29718+3805\sqrt{61})^2=29718^2+2\cdot 29718\cdot 3805\sqrt{61}+(3805\sqrt{61})^2. \end{align*} The middle coefficient is \begin{align*} 2\cdot 29718\cdot 3805=226153980. \end{align*} The last term is \begin{align*} (3805\sqrt{61})^2=3805^2\cdot 61=14478025\cdot 61=883159525. \end{align*} Substituting these values gives \begin{align*} (29718+3805\sqrt{61})^2=883159524+226153980\sqrt{61}+883159525. \end{align*} Combining the rational parts gives \begin{align*} (29718+3805\sqrt{61})^2=1766319049+226153980\sqrt{61}. \end{align*} The resulting positive Pell value calculation is \begin{align*} 1766319049^2=3119882982860264401. \end{align*} Also, \begin{align*} 226153980^2=51145622669840400. \end{align*} Multiplying by $61$ gives \begin{align*} 61\cdot 226153980^2=61\cdot 51145622669840400=3119882982860264400. \end{align*} Therefore \begin{align*} 1766319049^2-61\cdot 226153980^2=3119882982860264401-3119882982860264400=1. \end{align*} So the large first positive solution comes from a long continued-fraction period followed by one multiplication of the value-minus-one endpoint by itself; the method reaches it by a finite recurrence, while an unstructured search through all $y<226153980$ would be extremely inefficient. [/example] This large example is the standard warning that Pell equations can have small coefficients but very large smallest solutions. Continued fractions do not make the answer small; they make the search structured. ## The Negative Pell Equation and Period Parity The negative Pell equation asks when the value $-1$ occurs. The preceding results have already exposed the controlling invariant: the parity of the continued fraction period of $\sqrt{D}$. [definition: Negative Pell Equation] Let $D \in \mathbb N$ be not a square. The negative Pell equation associated to $D$ is \begin{align*} x^2-Dy^2=-1, \end{align*} with unknowns $x,y \in \mathbb Z$. [/definition] A negative solution is an integer pair with Pell value $-1$. Squaring the expression $x+y\sqrt D$ attached to such a pair always gives a positive Pell solution, but a positive solution need not arise this way. [quotetheorem:4502] [citeproof:4502] This criterion turns solvability of a Diophantine equation into a statement about the length of a finite block in a continued fraction. The nonsquare hypothesis is necessary because the period length is only available in the quadratic irrational case, and the integer solutions for square $D$ obey a different factorisation problem: for $D=4$, the equation \begin{align*} (x-2y)(x+2y)=-1 \end{align*} has no integer solutions, since the two factors would have to be $1$ and $-1$, which would force $4y=\pm 2$. Thus there is no positive negative-Pell solution and no period parity to inspect. The theorem does not claim that every positive Pell solution comes from squaring a negative one; it only decides whether value $-1$ occurs at all. It also explains why $D=2$ has $1^2-2\cdot 1^2=-1$, while $D=3$ has no negative Pell solution because $\sqrt{3}=[1;\overline{1,2}]$ has even period length. [example: Negative and Positive Pell for D Equals Two] For $D=2$, one has $\sqrt{2}=[1;\overline{2}]$, so the minimal period length is $L=1$. Since $L$ is odd, the odd-period criterion above shows that the negative Pell equation is soluble. The first convergent is $1/1$, and its Pell value is \begin{align*} 1^2-2\cdot 1^2=1-2=-1. \end{align*} Thus $1+\sqrt{2}$ has Pell value $-1$. Squaring this value-minus-one expression gives \begin{align*} (1+\sqrt{2})^2=1^2+2\cdot 1\cdot \sqrt{2}+(\sqrt{2})^2. \end{align*} Since $(\sqrt{2})^2=2$, this becomes \begin{align*} (1+\sqrt{2})^2=1+2\sqrt{2}+2=3+2\sqrt{2}. \end{align*} The corresponding positive Pell value is \begin{align*} 3^2-2\cdot 2^2=9-2\cdot 4=9-8=1. \end{align*} There is no positive solution with $y=1$, because $x^2-2=1$ would give $x^2=3$, which has no integer solution; with $y=2$ we get $x=3$. Hence $3+2\sqrt{2}$ is the first positive Pell solution, obtained by squaring the negative solution $1+\sqrt{2}$. [/example] The negative equation is therefore not an isolated side case. It is the odd-period route through which the positive equation is often reached. ## Generating All Positive Solutions After finding one positive solution, the final problem is to describe all the others. The multiplication identity suggests the answer: powers of the smallest positive value-one solution expression should generate the positive solutions. [definition: Fundamental Solution] Let $D \in \mathbb N$ be not a square. A fundamental solution of the positive Pell equation is a solution $(x_1,y_1) \in \mathbb N^2$ of \begin{align*} x_1^2-Dy_1^2=1 \end{align*} for which $x_1+y_1\sqrt{D}$ is the smallest real number among all expressions $x+y\sqrt D$ coming from positive integer solutions. [/definition] The order here is the ordinary order of real numbers. Since positive solutions give real numbers greater than $1$, the minimal such expression is the candidate generator for every other solution. [explanation: Generating Positive Pell Solutions] Let $(x_1,y_1)$ be the fundamental positive solution for $D$. Every positive solution $(x,y)$ of \begin{align*} x^2-Dy^2=1 \end{align*} is obtained by expanding \begin{align*} x+y\sqrt D=(x_1+y_1\sqrt D)^n \end{align*} for some integer $n\geq1$. [/explanation] This turns Pell's equation into a concrete recurrence for positive integer solutions. The positivity hypotheses matter: for $D=2$, the expression $3-2\sqrt{2}$ also has Pell value $1$, but it is less than $1$ and is not represented by a pair $(x,y)\in \mathbb N^2$ with both coordinates positive. The statement is therefore deliberately about positive solutions in $\mathbb N^2$. In computations, it means that the continued fraction period gives the fundamental positive solution, and ordinary multiplication then gives every later positive solution. [example: The Solution Sequence for D Equals Two] For $D=2$, the fundamental positive solution is $3+2\sqrt{2}$, so the generation theorem above gives every positive solution in the form \begin{align*} x_n+y_n\sqrt{2}=(3+2\sqrt{2})^n \end{align*} for some $n\in\mathbb N$. For $n=2$, expand the square: \begin{align*} (3+2\sqrt{2})^2=3^2+2\cdot 3\cdot 2\sqrt{2}+(2\sqrt{2})^2. \end{align*} Since $3^2=9$ and $(2\sqrt{2})^2=4\cdot 2=8$, this becomes \begin{align*} (3+2\sqrt{2})^2=9+12\sqrt{2}+8=17+12\sqrt{2}. \end{align*} The corresponding Pell value is \begin{align*} 17^2-2\cdot 12^2=289-2\cdot 144=289-288=1. \end{align*} For $n=3$, multiply the $n=2$ solution by the fundamental solution: \begin{align*} (3+2\sqrt{2})^3=(17+12\sqrt{2})(3+2\sqrt{2}). \end{align*} Expanding all four products gives \begin{align*} (17+12\sqrt{2})(3+2\sqrt{2})=17\cdot 3+17\cdot 2\sqrt{2}+12\sqrt{2}\cdot 3+12\sqrt{2}\cdot 2\sqrt{2}. \end{align*} The rational terms are $17\cdot 3=51$ and $12\sqrt{2}\cdot 2\sqrt{2}=24\cdot 2=48$, while the $\sqrt{2}$-terms are $17\cdot 2\sqrt{2}=34\sqrt{2}$ and $12\sqrt{2}\cdot 3=36\sqrt{2}$. Hence \begin{align*} (3+2\sqrt{2})^3=51+34\sqrt{2}+36\sqrt{2}+48=99+70\sqrt{2}. \end{align*} Its Pell value is \begin{align*} 99^2-2\cdot 70^2=9801-2\cdot 4900=9801-9800=1. \end{align*} Thus the sequence begins with $3+2\sqrt{2}$, then $17+12\sqrt{2}$, then $99+70\sqrt{2}$, and each later term is obtained by multiplying the previous one by the same fundamental solution expression. [/example] The chapter's conclusions can now be summarised as an algorithm. Compute the periodic continued fraction of $\sqrt{D}$; inspect the period length to decide whether the negative Pell equation is soluble; use one or two periods to find the fundamental positive solution; then raise the corresponding expression $x_1+y_1\sqrt D$ to successive powers to generate all positive solutions. # 9. Algorithms and Exact Computation Algorithms turn the theory of continued fractions into an exact computational tool. Chapters 1 through 4 treated convergents as mathematical objects with recurrence, determinant, and extremal approximation properties; here the same recurrences become finite procedures with certificates. The central questions are how to compute convergents without round-off ambiguity, how to reconstruct a small rational number from a congruence class, and how to prove that a proposed fraction is the intended approximation. ## Computing Convergents Without Floating Point Error The first computational problem is to evaluate a continued fraction while keeping control of the numerator and denominator at every stage. Decimal approximations can suggest the right answer, but the arithmetic of convergents is entirely integral, so exact computation should use integer recurrences. [definition: Convergent Recurrence] Let $a_0\in\mathbb Z$ and $a_i\in\mathbb N$ for $i\ge 1$. Define integers $p_n,q_n$ by \begin{align*} p_{-2}=0,\quad p_{-1}=1,\quad p_n=a_n p_{n-1}+p_{n-2},\qquad n\ge 0. \end{align*} The denominators are defined by the parallel recurrence \begin{align*} q_{-2}=1,\quad q_{-1}=0,\quad q_n=a_n q_{n-1}+q_{n-2},\qquad n\ge 0. \end{align*} [/definition] The recurrence is the computational form of the finite continued fraction $[a_0; a_1,\dots,a_n]$. To use it as an algorithm, we must prove that the integers it produces really evaluate the continued fraction and that the numerator and denominator stay coprime. [quotetheorem:5521] [citeproof:5521] The assumptions on the partial quotients are part of the certificate. If some later $a_i$ were allowed to be $0$, the denominators need not increase in the usual way; for instance $[1;0,2]$ collapses the reciprocal step and no longer represents the standard continued-fraction expansion. The theorem also does not say that a real input has been identified correctly: it only verifies the exact fraction attached to a given finite list of partial quotients. That distinction is why the next algorithm must explain how the partial quotients themselves are obtained. This theorem is the basic correctness certificate for the standard algorithm: store only the previous two numerator-denominator pairs, update by integer multiplication and addition, and output $p_n/q_n$. The determinant identity is also a built-in coprimality check, since it implies $\gcd(p_n,q_n)=1$. [example: Exact Convergents for 415 Over 93] For $415/93$, the Euclidean divisions are \begin{align*} 415=4\cdot 93+43. \end{align*} \begin{align*} 93=2\cdot 43+7. \end{align*} \begin{align*} 43=6\cdot 7+1. \end{align*} \begin{align*} 7=7\cdot 1+0. \end{align*} Dividing each nonterminal identity by its divisor gives \begin{align*} \frac{415}{93}=4+\frac{43}{93}=4+\frac{1}{93/43}. \end{align*} \begin{align*} \frac{93}{43}=2+\frac{7}{43}=2+\frac{1}{43/7}. \end{align*} \begin{align*} \frac{43}{7}=6+\frac{1}{7}=6+\frac{1}{7/1}. \end{align*} \begin{align*} \frac{7}{1}=7. \end{align*} Substituting from the bottom upward, \begin{align*} \frac{43}{7}=6+\frac{1}{7}. \end{align*} \begin{align*} \frac{93}{43}=2+\frac{1}{6+\frac{1}{7}}. \end{align*} \begin{align*} \frac{415}{93}=4+\frac{1}{2+\frac{1}{6+\frac{1}{7}}}=[4;2,6,7]. \end{align*} Now use the convergent recurrence with $a_0=4$, $a_1=2$, $a_2=6$, and $a_3=7$, starting from $p_{-2}=0$, $p_{-1}=1$, $q_{-2}=1$, and $q_{-1}=0$. The numerator recurrence gives \begin{align*} p_0=4p_{-1}+p_{-2}=4\cdot 1+0=4. \end{align*} \begin{align*} p_1=2p_0+p_{-1}=2\cdot 4+1=9. \end{align*} \begin{align*} p_2=6p_1+p_0=6\cdot 9+4=54+4=58. \end{align*} \begin{align*} p_3=7p_2+p_1=7\cdot 58+9=406+9=415. \end{align*} The denominator recurrence gives \begin{align*} q_0=4q_{-1}+q_{-2}=4\cdot 0+1=1. \end{align*} \begin{align*} q_1=2q_0+q_{-1}=2\cdot 1+0=2. \end{align*} \begin{align*} q_2=6q_1+q_0=6\cdot 2+1=12+1=13. \end{align*} \begin{align*} q_3=7q_2+q_1=7\cdot 13+2=91+2=93. \end{align*} Therefore the successive convergents are \begin{align*} \frac{p_0}{q_0}=\frac{4}{1},\quad \frac{p_1}{q_1}=\frac{9}{2},\quad \frac{p_2}{q_2}=\frac{58}{13},\quad \frac{p_3}{q_3}=\frac{415}{93}. \end{align*} The Euclidean quotients $4,2,6,7$ are exactly the partial quotients used by the recurrence, so the Euclidean algorithm and the convergent recurrence encode the same integer computation. [/example] ## The Euclidean Algorithm as a Verified Procedure The next problem is to justify the finite algorithm that produces the partial quotients. The recurrence assumes the list $a_0,\dots,a_n$ has already been found; the Euclidean algorithm is the exact procedure that finds it for rational inputs. [quotetheorem:5522] [citeproof:5522] The condition $B>0$ and the choice $0\le r_{i+1}<r_i$ are what make this a terminating algorithm rather than merely an identity. If the remainder were not required to be smaller, one could keep replacing $(A,B)$ by pairs with the same gcd without making progress, for example by writing $A=0\cdot B+A$ repeatedly when $A>B$. The theorem identifies the gcd and the continued-fraction quotients for rational inputs; it does not address reconstruction from residues, where the original numerator and denominator are hidden. The proof matters computationally because it gives a loop invariant: replacing $(r_{i-1},r_i)$ by $(r_i,r_{i+1})$ does not change the gcd. In exact computation, such invariants are the difference between a numerical guess and a verifiable algorithm. [remark: Size of the Computation] If the input integers have at most $N$ decimal digits, the number of Euclidean divisions is $O(N)$ in the worst case. The slow case occurs when the quotients are mostly $1$, as in consecutive Fibonacci numbers, because the remainders then decrease as slowly as possible for this recurrence. [/remark] The Euclidean algorithm also appears in reverse in rational reconstruction. There, the input is not a rational number but a residue class modulo $m$, and the goal is to find the small numerator and denominator that produced it. ## Rational Reconstruction from Modular Data Suppose a computation modulo $m$ returns a residue $x$. If the true rational answer was $p/q$, with $\gcd(q,m)=1$, then modular arithmetic sees only \begin{align*} x\equiv p q^{-1}\pmod m. \end{align*} The reconstruction problem asks when this congruence determines $p/q$ uniquely among all fractions with prescribed size bounds. [definition: Rational Reconstruction Candidate] Let $m\in\mathbb N$, let $x\in\mathbb Z/m\mathbb Z$, and let $P,Q\in\mathbb N$. A rational reconstruction candidate for $(x,m;P,Q)$ is a pair $(p,q)\in\mathbb Z\times\mathbb N$ such that \begin{align*} |p|\le P,\quad q\le Q,\quad \gcd(p,q)=1,\quad \gcd(q,m)=1,\quad p\equiv xq\pmod m. \end{align*} [/definition] The congruence says that $p/q$ reduces to $x$ modulo $m$. The size bounds are part of the data because, without them, many different fractions can have the same residue. The key obstruction is collision: two candidates with small numerator and denominator must be forced to have the same cross-product before uniqueness can be certified. [quotetheorem:5523] [citeproof:5523] The inequality $2PQ<m$ is the practical certification condition. It says that the modulus must be large enough to distinguish all possible cross-products $pq'$ and $p'q$ within the allowed search box. If equality is allowed, uniqueness can fail: with $m=2$, $P=1$, and $Q=1$, the distinct reduced fractions $1/1$ and $-1/1$ both reduce to $1$ modulo $2$, and the denominator $1$ is invertible modulo $2$. The theorem also does not promise that a candidate exists; it gives a uniqueness certificate and a verified search procedure when the size information is strong enough. [example: Reconstructing 17 Over 43 Modulo 1000] Let $x=419$ modulo $1000$. First verify the modular inverse used to produce this residue: \begin{align*} 43\cdot 907=39001=39\cdot 1000+1. \end{align*} Thus $43\cdot 907\equiv 1\pmod{1000}$, so $43^{-1}\equiv 907\pmod{1000}$. Therefore \begin{align*} 17\cdot 43^{-1}\equiv 17\cdot 907\pmod{1000}. \end{align*} The product is \begin{align*} 17\cdot 907=15419=15\cdot 1000+419, \end{align*} so \begin{align*} 17\cdot 43^{-1}\equiv 419\pmod{1000}. \end{align*} Thus $17/43$ really reduces to the residue $419$ modulo $1000$. Take $P=20$ and $Q=50$. The target fraction lies inside these bounds because $|17|=17\le 20$ and $43\le 50$, and the coprimality conditions hold: \begin{align*} \gcd(17,43)=1. \end{align*} Also \begin{align*} \gcd(43,1000)=1. \end{align*} However, the modulus is too small for the uniqueness condition in the [rational reconstruction theorem](/theorems/5523), since \begin{align*} 2PQ=2\cdot 20\cdot 50=2000. \end{align*} The required inequality would be $2000<1000$, which is false. Hence modulus $1000$ does not certify uniqueness for the box $|p|\le 20$, $q\le 50$. If the bounds are tightened to $P=17$ and $Q=20$, then the modulus inequality becomes \begin{align*} 2PQ=2\cdot 17\cdot 20=680<1000. \end{align*} But the intended denominator no longer fits the search box, because \begin{align*} 43>20. \end{align*} So the first choice of bounds contains $17/43$ but fails the uniqueness inequality, while the second choice satisfies the inequality but excludes $17/43$. Successful reconstruction needs both conditions at once: the bounds must contain the target, and they must satisfy $2PQ<m$. [/example] The preceding example is useful because it exposes a common failure mode: knowing a residue modulo $1000$ is not by itself enough for these bounds. To certify $17/43$ with $Q\ge 43$, one must increase the modulus or sharpen the numerator bound enough that $2PQ<m$. [example: Certified Reconstruction of 17 Over 43] Use the same rational number, but take modulus $m=2000$ and compute the residue of $17/43$ modulo $2000$. First verify the inverse of $43$: \begin{align*} 43\cdot 1907=43(1900+7)=81700+301=82001=41\cdot 2000+1. \end{align*} Hence $43\cdot 1907\equiv 1\pmod{2000}$, so $43^{-1}\equiv 1907\pmod{2000}$. Therefore \begin{align*} 17\cdot 43^{-1}\equiv 17\cdot 1907\pmod{2000}. \end{align*} The product is \begin{align*} 17\cdot 1907=17(1900+7)=32300+119=32419=16\cdot 2000+419, \end{align*} so \begin{align*} 17\cdot 43^{-1}\equiv 419\pmod{2000}. \end{align*} Thus the residue is $x\equiv 419\pmod{2000}$. Take $P=20$ and $Q=49$. The pair $(p,q)=(17,43)$ satisfies the size bounds because \begin{align*} |17|=17\le 20 \end{align*} and \begin{align*} 43\le 49. \end{align*} It is reduced: the Euclidean divisions \begin{align*} 43=2\cdot 17+9 \end{align*} \begin{align*} 17=1\cdot 9+8 \end{align*} \begin{align*} 9=1\cdot 8+1 \end{align*} \begin{align*} 8=8\cdot 1+0 \end{align*} show that $\gcd(17,43)=1$. The denominator is also invertible modulo $2000$, since \begin{align*} 2000=46\cdot 43+22 \end{align*} \begin{align*} 43=1\cdot 22+21 \end{align*} \begin{align*} 22=1\cdot 21+1 \end{align*} \begin{align*} 21=21\cdot 1+0 \end{align*} show that $\gcd(43,2000)=1$. Finally, the congruence condition holds because \begin{align*} 419\cdot 43=419(40+3)=16760+1257=18017=9\cdot 2000+17, \end{align*} so \begin{align*} 17\equiv 419\cdot 43\pmod{2000}. \end{align*} The uniqueness inequality required by the rational reconstruction theorem is satisfied: \begin{align*} 2PQ=2\cdot 20\cdot 49=40\cdot 49=1960<2000. \end{align*} Thus $17/43$ is not only a candidate in the box $|p|\le 20$, $q\le 49$; it is the unique reduced fraction in that box whose denominator is invertible modulo $2000$ and whose reduction is $419$. [/example] ## Error Certification for Continued Fraction Approximation The final computational question is how to prove that a fraction recovered from decimal or real-number data is the desired best approximation. Continued fractions provide stopping criteria that use only a denominator bound and an error estimate. [explanation: Convergent Error Bound] For an irrational simple continued fraction with convergents $p_n/q_n$, the standard error estimate gives \begin{align*} \left|\theta-\frac{p_n}{q_n}\right|<\frac{1}{q_nq_{n+1}}. \end{align*} [/explanation] The irrationality hypothesis avoids the terminal case of a finite continued fraction. For a rational number the next denominator $q_{n+1}$ may not exist after the expansion ends, so the same bound cannot be used as an infinite-process certificate; for example $1/2=[0;2]$ has no following convergent in its standard finite expansion. The theorem gives an error bound for convergents, not a converse saying every fraction with this error must be a convergent. The next result adds a denominator budget to turn the bound into a stopping rule. This estimate provides an a posteriori certificate: once $q_{n+1}$ is known, the error of $p_n/q_n$ is bounded without knowing any later partial quotients. It also leads to a stopping rule for approximation under a denominator budget. [explanation: Continued Fraction Stopping Certificate] Let $\theta\in\mathbb R\setminus\mathbb Q$, let $N\in\mathbb N$, and let $n$ be the index with \begin{align*} q_n\leq N<q_{n+1}. \end{align*} The candidate $p_n/q_n$ is the last convergent below the denominator budget. To certify uniqueness from numerical data, record the error bound \begin{align*} \left|\theta-\frac{p_n}{q_n}\right|<\frac{1}{2N^2}. \end{align*} Then no other reduced rational $a/b$ with $1\leq b\leq N$ can satisfy the same strict error inequality. [/explanation] The strict uniqueness inequality is doing real work. The scale comes from neighbouring reduced fractions: for example, $1/N$ and $1/(N-1)$ have denominators at most $N$ and are separated by $1/(N(N-1))$, so their midpoint is within $1/(2N(N-1))$ of both. This is slightly larger than $1/(2N^2)$ and shows why the denominator-squared scale is the right one. The result certifies uniqueness inside an error interval; it does not claim that the last convergent below $N$ is always the globally best rational of denominator at most $N$ unless the relevant best-approximation theorem has also been invoked. This criterion is especially useful when a real number is given only numerically. The computation must separate two tasks: first produce a candidate rational, then certify that all possible rational competitors under the denominator bound have been excluded. [example: Certified Decimal-to-Rational Recovery] Suppose a computation gives a real number $\theta$ with certified enclosure \begin{align*} |\theta-0.3953488372093|<10^{-13}, \end{align*} and we want to recover a rational with denominator at most $50$. Test the candidate $17/43$. Since \begin{align*} 0.3953488372093=\frac{3953488372093}{10^{13}}, \end{align*} its distance from the displayed decimal can be computed exactly: \begin{align*} \left|\frac{3953488372093}{10^{13}}-\frac{17}{43}\right|=\left|\frac{43\cdot 3953488372093-17\cdot 10^{13}}{43\cdot 10^{13}}\right|. \end{align*} The numerator is \begin{align*} 43\cdot 3953488372093=169999999999999 \end{align*} and \begin{align*} 17\cdot 10^{13}=170000000000000, \end{align*} so \begin{align*} \left|\frac{3953488372093}{10^{13}}-\frac{17}{43}\right|=\frac{1}{430000000000000}. \end{align*} Because \begin{align*} 4\cdot 10^{-14}=\frac{4}{10^{14}}=\frac{1}{25000000000000} \end{align*} and \begin{align*} 430000000000000>25000000000000, \end{align*} we get \begin{align*} \left|0.3953488372093-\frac{17}{43}\right|<4\cdot 10^{-14}. \end{align*} By the triangle inequality, \begin{align*} \left|\theta-\frac{17}{43}\right|\le |\theta-0.3953488372093|+\left|0.3953488372093-\frac{17}{43}\right|. \end{align*} Using the two bounds just obtained, \begin{align*} \left|\theta-\frac{17}{43}\right|<10^{-13}+4\cdot 10^{-14}=1.4\cdot 10^{-13}. \end{align*} For the denominator bound $N=50$, the uniqueness threshold in the continued-fraction stopping criterion is \begin{align*} \frac{1}{2N^2}=\frac{1}{2\cdot 50^2}=\frac{1}{2\cdot 2500}=\frac{1}{5000}=2\cdot 10^{-4}. \end{align*} Since \begin{align*} 1.4\cdot 10^{-13}<2\cdot 10^{-4}, \end{align*} the certified error is smaller than $1/(2N^2)$. Therefore $17/43$ is the unique rational number with denominator at most $50$ compatible with the certified computation. [/example] ## Exact Computation as a Pattern The common danger in these algorithms is stopping because the answer looks plausible rather than because all competitors have been excluded. The algorithms in this chapter avoid that danger by following the same pattern. First, translate the mathematical object into integer recurrences or Euclidean remainders. Next, keep an invariant: a determinant identity, a gcd equality, or a modular congruence. Finally, stop only when an inequality gives a certificate that no other candidate in the permitted range can satisfy the same data. [remark: What the Certificate Records] A useful certificate for a computed approximation should record the input bounds, the partial quotients or Euclidean quotients used, the candidate $p/q$, and the final inequality excluding competitors. For rational reconstruction, this means recording $P,Q,m,x$ and checking $2PQ<m$. For decimal-to-rational recovery, this means recording the real-number error enclosure and the denominator bound $N$. [/remark] In the Pell and quadratic-irrational computations of Chapters 6 through 8, these certificates prevent numerical experiments from being mistaken for proofs. Continued fractions are effective because each approximation arrives with enough integer arithmetic to verify why it is the correct one. # 10. Synthesis and Further Directions The course has developed continued fractions from several directions: the Euclidean algorithm, convergents, best approximation, quadratic periodicity, and Pell equations. This final chapter is an optional synthesis. It gathers the earlier strands into two concrete viewpoints that need only the tools already used in the course: an interval map that shifts continued-fraction tails, and products of $2\times2$ integer matrices that package the same numerator-denominator recurrences. ## The Gauss Map and Complete Quotients What dynamical system is hidden inside the operation of repeatedly taking reciprocals and subtracting integer parts? For an irrational $x \in (0,1)$, the continued fraction algorithm replaces $x$ by the fractional part of $1/x$. This operation does not merely compute digits; it moves $x$ through a sequence of intervals labelled by the partial quotients. [definition: Gauss Map] The Gauss map is the function $T:(0,1)\setminus \mathbb Q \to (0,1)\setminus \mathbb Q$ defined by \begin{align*} T(x) = \left\{\frac{1}{x}\right\} = \frac{1}{x} - \left\lfloor \frac{1}{x}\right\rfloor . \end{align*} [/definition] The integer $\lfloor 1/x\rfloor$ records the next partial quotient. Thus the forward orbit of $x$ under repeated applications of $T$ is the same information as the tail sequence of the continued fraction, but written as an interval map. Complete quotients make this identification explicit and prevent a common ambiguity: the Gauss map sees the fractional tails $[0;a_n,a_{n+1},\dots]$, while the continued fraction algorithm also keeps the integer-leading tails $[a_n;a_{n+1},\dots]$. Naming the complete quotients separates these two related objects and exposes exactly which part of the expansion is shifted away at each step. [definition: Complete Quotients] Let $\theta \in \mathbb R\setminus \mathbb Q$ have continued fraction expansion $\theta=[a_0;a_1,a_2,\dots]$. The $n$th complete quotient is \begin{align*} \theta_n = [a_n;a_{n+1},a_{n+2},\dots] \end{align*} for $n\geq 0$. [/definition] For the fractional part $x=\theta-a_0=[0;a_1,a_2,\dots]$, the point obtained after applying $T$ exactly $n-1$ times is \begin{align*} [0;a_n,a_{n+1},\dots] \end{align*} for $n\geq 1$. The next question is how the first digit $a_n$ is visible before the rest of the tail is known. The answer is that $(0,1)$ is cut into countably many intervals, and on each interval the Gauss map has a simple inverse branch. This interval structure is the dynamical version of choosing the next partial quotient. The next theorem makes this branch decomposition precise, turning the informal rule "take the integer part of $1/x$" into an exact partition and inverse-branch statement. This matters because the digit $a_1$ is not chosen after computing the whole expansion; it is already determined by the location of $x$ in one interval. Since $0<x<1$, we have $1/x>1$, so the integer part that appears as the first positive partial quotient is forced to satisfy $k\geq 1$. [quotetheorem:5524] [citeproof:5524] This theorem turns the algorithm into a labelled interval process: each iterate lands in exactly one branch interval, and the branch labels are the continued fraction digits. The condition $k\geq 1$ is not an extra convention; it follows from $x\in(0,1)$, since then $1/x>1$ and the integer part cannot be $0$. The exclusion of rational points is essential because a rational continued fraction terminates, so some iterate reaches $0$ rather than remaining inside $(0,1)$. The endpoints $1/k$ are also excluded from the open intervals because they correspond to the boundary between two possible integer-part inequalities; treating them would require a separate terminating convention rather than the uniform irrational algorithm. What the theorem does not say is that the orbit has any simple long-term pattern: the interval labels may be arbitrary, eventually periodic, or non-periodic. The next example isolates the simplest possible long-term pattern, namely a fixed point of the Gauss map. [example: Orbit of Sqrt Two Minus One] Let $x=\sqrt{2}-1$. Since $1<\sqrt{2}<2$, we have $0<\sqrt{2}-1<1$, so $x\in(0,1)$. To compute its reciprocal, multiply numerator and denominator by the conjugate: \begin{align*} \frac{1}{x}=\frac{1}{\sqrt{2}-1}. \end{align*} \begin{align*} \frac{1}{\sqrt{2}-1}=\frac{\sqrt{2}+1}{(\sqrt{2}-1)(\sqrt{2}+1)}. \end{align*} \begin{align*} (\sqrt{2}-1)(\sqrt{2}+1)=(\sqrt{2})^2-1^2=2-1=1. \end{align*} Hence \begin{align*} \frac{1}{x}=\sqrt{2}+1. \end{align*} Because $1<\sqrt{2}<2$, we also have $2<\sqrt{2}+1<3$, so $\left\lfloor 1/x\right\rfloor=2$. Therefore the Gauss map gives \begin{align*} T(x)=\frac{1}{x}-\left\lfloor \frac{1}{x}\right\rfloor. \end{align*} \begin{align*} T(x)=(\sqrt{2}+1)-2=\sqrt{2}-1=x. \end{align*} Thus $x$ is a fixed point of the Gauss map. Since every iterate is again $x$ and the branch label is always $2$, the continued fraction digits repeat: \begin{align*} x=[0;2,2,2,\dots]. \end{align*} This is the one-symbol periodic case: the repeating block $(2)$ gives a fixed point of $T$, while a repeating block of length $r>1$ gives an orbit whose period divides $r$. By contrast, an irrational such as $[0;1,2,3,4,\dots]$ has tails with first digits $1,2,3,4,\dots$, so no tail can repeat and its Gauss orbit is not eventually periodic. [/example] The fixed point in the example is the simplest non-rational periodic orbit, but examples alone do not distinguish a genuine dynamical pattern from a coincidence of one quadratic irrational. The obstruction is that a continued fraction tail could fail to return exactly, giving an infinite nonrepeating Gauss orbit even though each individual step is well defined. The classification problem is to identify exactly when the Gauss orbit eventually repeats, so that periodicity of continued fractions becomes a dynamical condition rather than a visual pattern in the digits. The point is not merely to recognize a repeated block once it has been written down, but to know which numbers force such a repetition after finitely many Gauss steps. The obstruction is arithmetic: a tail of a continued fraction is again a number of the same kind, but only special irrational numbers return to a previous tail. The theorem below gives the exact criterion, turning the dynamical condition of an eventually periodic orbit into the arithmetic condition of being a quadratic irrational. [quotetheorem:1763] [citeproof:1763] This viewpoint explains why complete quotients were the natural language for quadratic irrationals. They are not auxiliary variables; they are the points in the orbit of the continued fraction dynamical system. The irrationality hypothesis matters in a concrete way: if \begin{align*} x=[0;2,3]=\frac{3}{7}, \end{align*} then the first Gauss iterate is \begin{align*} T(x)=\frac{1}{3}, \end{align*} and the next reciprocal step reaches an endpoint rather than another irrational point of $(0,1)$. Thus rational numbers have finite continued fractions, so their Gauss trajectories terminate instead of becoming periodic inside the irrational state space. The distinction between eventual and pure periodicity is also dynamical. An expansion such as $[0;1,2,\overline{3,4}]$ has an orbit that becomes periodic after the non-repeating prefix has been shifted away, whereas $[0;\overline{3,4}]$ lies on the periodic orbit from the start. The theorem therefore classifies tails, not initial finite prefixes, and it has a precise limitation: eventual periodicity is not a statement that the approximation constants are the same for all quadratic irrationals. For example, different periodic blocks give different convergent growth and hence different Diophantine behaviour. To compare those periodic blocks efficiently, it is useful to replace the recurrence formulas by products of integer matrices. ## Matrix Products and Fractional Linear Transformations How can the same continued fraction data be read from linear algebra? Every finite continued fraction is built by composing maps of the form $z\mapsto a+1/z$. These maps are fractional linear transformations, so they are represented by $2\times 2$ integer matrices. [definition: Continued Fraction Matrix] The continued fraction matrix map sends an integer $a$ to the $2\times2$ integer matrix $M(a)$ whose first row is $(a,1)$ and whose second row is $(1,0)$. For each $n\geq 0$, the finite-word product is \begin{align*} M_n(a_0,\dots,a_n)=M(a_0)M(a_1)\cdots M(a_n). \end{align*} [/definition] The determinant of $M(a)$ is $-1$, so products alternate between determinant $1$ and determinant $-1$. The reason to introduce these matrices is that their entries are not extra data: they are exactly the numerator and denominator recurrences already used for convergents. The following formula packages the continuant identities into a single matrix identity and recovers the determinant identity as its determinant. [quotetheorem:5502] [citeproof:5502] The formula packages the whole recurrence into one object. The initial values in the theorem are not cosmetic: without $p_{-2}=0$, $p_{-1}=1$, $q_{-2}=1$, and $q_{-1}=0$, the first matrix product would not simultaneously encode the $n$th and $(n-1)$st convergents. The simple continued fraction hypothesis is also doing work, since positivity of the later partial quotients is what makes the denominators increase and supports the approximation interpretation from earlier chapters. A direct consequence is that convergents are reduced fractions: a common divisor of $p_n$ and $q_n$ would divide the determinant $p_nq_{n-1}-p_{n-1}q_n$. The limitation is that the matrix identity alone records exact algebraic recurrences, not which convergents are best approximations; for that one still needs the order and interval arguments proved earlier. The same matrices become more powerful when a block repeats, because then a period is compressed into a single fractional linear transformation. [example: Reading a Period from a Matrix Fixed Point] Consider the repeating block $(2)$, represented by the matrix $M(2)$ whose first row is $(2,1)$ and whose second row is $(1,0)$. The associated fractional linear transformation sends a positive tail $z$ to \begin{align*} \frac{2z+1}{z}=2+\frac{1}{z}. \end{align*} Thus a fixed point for the one-term repeating block satisfies \begin{align*} z=2+\frac{1}{z}. \end{align*} Since a continued fraction tail is positive, $z>0$, so multiplying by $z$ gives \begin{align*} z^2=2z+1. \end{align*} Equivalently, \begin{align*} z^2-2z-1=0. \end{align*} Using the quadratic formula, \begin{align*} z=\frac{2\pm\sqrt{(-2)^2-4(1)(-1)}}{2}. \end{align*} The discriminant is \begin{align*} (-2)^2-4(1)(-1)=4+4=8. \end{align*} Hence \begin{align*} z=\frac{2\pm\sqrt{8}}{2}. \end{align*} Since $\sqrt{8}=2\sqrt{2}$, this becomes \begin{align*} z=1\pm\sqrt{2}. \end{align*} Because $\sqrt{2}>1$, the root $1-\sqrt{2}$ is negative, while the continued fraction tail $[2;2,2,\dots]$ is positive. Therefore \begin{align*} [2;2,2,\dots]=1+\sqrt{2}. \end{align*} Taking the reciprocal gives \begin{align*} [0;2,2,\dots]=\frac{1}{1+\sqrt{2}}. \end{align*} Rationalizing the denominator, \begin{align*} \frac{1}{1+\sqrt{2}}=\frac{\sqrt{2}-1}{(1+\sqrt{2})(\sqrt{2}-1)}. \end{align*} The denominator is \begin{align*} (1+\sqrt{2})(\sqrt{2}-1)=(\sqrt{2})^2-1^2=2-1=1. \end{align*} Thus \begin{align*} [0;2,2,\dots]=\sqrt{2}-1. \end{align*} The matrix fixed point for the period $(2)$ therefore recovers the same number as the Gauss map fixed point above. [/example] For a longer period, one multiplies the matrices attached to the block and studies the fixed points of the resulting fractional linear transformation. Those fixed points are roots of a quadratic equation because the fixed-point equation has degree two. [remark: Determinant Sign] Each factor has determinant $-1$. Therefore a product with an even number of factors has determinant $1$, while a product with an odd number of factors has determinant $-1$. The sign records orientation, but the entries still encode the same convergent numerators and denominators. [/remark] The matrix viewpoint is especially useful when comparing equivalent quadratic irrationals. Changing the starting point in a periodic block cycles the same product data, so the repeating tail is changed in presentation but not in arithmetic content. ## Outlook: Approximation Constants Where do the best approximation theorems lead beyond this course? Chapter 5 showed that every irrational $\theta$ has infinitely many rational approximations $p/q$ with $|\theta-p/q|<1/q^2$, and that bounded partial quotients are exactly the badly approximable numbers. A natural optional next question is how small the products $q\|q\theta\|$ can get along infinitely many denominators, where $\|q\theta\|$ is the distance from $q\theta$ to the nearest integer. [definition: Markov Constant] The Markov constant is the function \begin{align*} \mu:\mathbb R\setminus\mathbb Q\to (0,\infty] \end{align*} defined by the element-mapping rule \begin{align*} \theta\mapsto \left(\liminf_{q\to\infty} q\,\|q\theta\|\right)^{-1}, \end{align*} with the convention that $1/0=\infty$. [/definition] Large values of $\mu(\theta)$ mean that $\theta$ admits unusually strong rational approximation along infinitely many denominators. This definition is included as an outlook, not as a new theorem to prove here. The point is that the same convergent estimates used throughout the course are the first tools one uses to compute or bound this constant. [example: A Convergent Computation for Square Root Two] For $\sqrt{2}=[1;\overline{2}]$, the convergents satisfy the Pell identity \begin{align*} p_n^2-2q_n^2=\pm 1. \end{align*} Hence \begin{align*} |q_n\sqrt{2}-p_n|=\frac{1}{p_n+q_n\sqrt{2}}, \end{align*} and therefore \begin{align*} q_n\|q_n\sqrt{2}\|=\frac{q_n}{p_n+q_n\sqrt{2}}. \end{align*} Since $p_n/q_n\to\sqrt{2}$, the denominator divided by $q_n$ tends to $2\sqrt{2}$, so these convergent values tend to \begin{align*} \frac{1}{2\sqrt{2}}. \end{align*} Thus the convergents contribute the reciprocal limiting value \begin{align*} 2\sqrt{2}. \end{align*} In the full theory, the best-approximation properties proved earlier show that non-convergent denominators do not lower the relevant liminf here. The example is meant only as a computation; the broader theory asks which constants occur for all irrational numbers. [/example] For the synthesis here, the important point is that continued fractions remain the main computational language even beyond the elementary course: long-term approximation constants are read from partial quotients, convergents, and complete quotients. ## Review Problems and Course-Level Synthesis What should a reader be able to do after the course? The central skill is to move between algorithms, estimates, periodicity, and equations without treating them as separate subjects. The following synthesis records the main equivalences and techniques that the preceding chapters developed. [remark: Main Equivalences for Continued Fractions] For a real irrational number $\theta$, the following principles summarise the course. 1. The continued fraction digits of $\theta$ are generated by the complete quotient algorithm. 2. The convergents $p_n/q_n$ are encoded by products of the matrices $M(a_n)$. 3. The convergents give best rational approximations in the sense of the comparison theorems proved earlier. 4. The continued fraction of $\theta$ is eventually periodic if and only if $\theta$ is a quadratic irrational. 5. Period parity for $\sqrt{D}$ governs the solvability of $x^2-Dy^2=-1$ in integers. 6. The partial quotients of $\theta$ are bounded if and only if $\theta$ is badly approximable. [/remark] This summary is a map of the course rather than a new result. The irrationality hypothesis is necessary throughout: rational numbers have terminating continued fractions, so their complete quotients and approximation behaviour must be treated with endpoint conventions. Each principle also has a limitation. The matrix product records convergents but does not by itself prove best approximation; eventual periodicity characterises quadratic irrationals but does not make all quadratic irrationals arithmetically identical; and the Pell parity criterion is specific to expansions of $\sqrt D$, not to arbitrary quadratic irrationals. The suggested exercises ask the reader to move along these links while keeping those hypotheses visible. [example: Certifying a Best Approximation Below a Denominator Bound] Take $\theta=\sqrt{2}$ and use the denominator bound $1000$. Since \begin{align*} \sqrt{2}=1+(\sqrt{2}-1) \end{align*} and \begin{align*} \frac{1}{\sqrt{2}-1} =\frac{\sqrt{2}+1}{(\sqrt{2}-1)(\sqrt{2}+1)} =\frac{\sqrt{2}+1}{2-1} =\sqrt{2}+1 =2+(\sqrt{2}-1), \end{align*} the same fractional tail repeats, so \begin{align*} \sqrt{2}=[1;2,2,2,\dots]. \end{align*} The convergent denominators are computed from $q_{-2}=1$, $q_{-1}=0$, and $q_n=a_nq_{n-1}+q_{n-2}$. Thus \begin{align*} q_0=1\cdot 0+1=1. \end{align*} \begin{align*} q_1=2\cdot 1+0=2. \end{align*} \begin{align*} q_2=2\cdot 2+1=5. \end{align*} \begin{align*} q_3=2\cdot 5+2=12. \end{align*} \begin{align*} q_4=2\cdot 12+5=29. \end{align*} \begin{align*} q_5=2\cdot 29+12=70. \end{align*} \begin{align*} q_6=2\cdot 70+29=169. \end{align*} \begin{align*} q_7=2\cdot 169+70=408. \end{align*} \begin{align*} q_8=2\cdot 408+169=985. \end{align*} \begin{align*} q_9=2\cdot 985+408=2378. \end{align*} The numerator recurrence, with $p_{-2}=0$ and $p_{-1}=1$, gives \begin{align*} p_6=2\cdot 99+41=239. \end{align*} \begin{align*} p_7=2\cdot 239+99=577. \end{align*} \begin{align*} p_8=2\cdot 577+239=1393. \end{align*} Hence the last convergent denominator below $1000$ is \begin{align*} \frac{p_8}{q_8}=\frac{1393}{985}, \end{align*} and the denominator straddling is \begin{align*} 985\leq 1000<2378. \end{align*} The stopping certificate from Chapter 9 uses an error threshold rather than a separate classification theorem. The Pell calculation \begin{align*} 1393^2-2\cdot 985^2=-1 \end{align*} gives \begin{align*} \left|\sqrt{2}-\frac{1393}{985}\right|=\frac{1}{985(1393+985\sqrt{2})}. \end{align*} Since $\sqrt{2}>1$, the denominator is greater than \begin{align*} 985(1393+985)=985\cdot 2378=2342330. \end{align*} Therefore \begin{align*} \left|\sqrt{2}-\frac{1393}{985}\right|<\frac{1}{2342330}<\frac{1}{2\cdot 1000^2}. \end{align*} The continued-fraction stopping certificate now applies with $N=1000$. Thus $1393/985$ is the unique reduced rational with denominator at most $1000$ whose error is below $1/(2\cdot1000^2)$. In particular, no rational with denominator at most $1000$ can have a smaller error, because any smaller error would also lie below the same threshold. [/example] The synthesis of the course is that continued fractions are simultaneously an algorithm, a sequence of rational approximations, a labelled interval process, and a matrix product. The same digits $a_n$ control Euclidean remainders, approximation quality, quadratic periods, Pell solutions, and long-term approximation constants. That unity is why continued fractions remain a central tool in elementary and advanced number theory. ## References - Internal Androma references: - [Cambridge II Number Theory](/page/Cambridge%20II%20Number%20Theory), for the surrounding elementary number theory background. - [Diophantine Equations](/page/Diophantine%20Equations), for the arithmetic setting of Pell equations and integral solutions. - [Lagrange's Theorem for Square Root Continued Fractions](/theorems/4498), for periodic square-root expansions. - [Lagrange - Periodicity Characterises Quadratic Irrationals](/theorems/1763), for the equivalence between quadratic irrationality and eventual periodicity. - [Convergents Give Pell Solutions](/theorems/4499), for the bridge from period endpoints to Pell equations. - [Odd Period Criterion for the Negative Pell Equation](/theorems/4502), for the parity criterion used in the Pell chapter. - A. Ya. Khinchin, *Continued Fractions*. - G. H. Hardy and E. M. Wright, *An Introduction to the Theory of Numbers*. - A. M. Rockett and P. Szusz, *Continued Fractions*.