Motivation
A rational approximation is useful only after its accuracy is compared with the size of its denominator. Continued fractions construct fractions with a particularly strong relationship between those two quantities. The construction repeatedly removes an integer part and reciprocates the remainder. Its arithmetic is the Euclidean algorithm for rational inputs, while irrational inputs produce an infinite sequence whose finite approximations converge with explicit error bounds.
The determinant of two neighboring approximations will be the key invariant. It says that the corresponding integer pairs form a basis of the integer lattice. Expressing any competing rational in that basis turns an approximation claim into a sign argument. We will then prove a useful converse criterion: an exceptionally accurate reduced fraction must already occur among the convergents.
The input is a positive real number. Exact comparisons and identities are used in proofs; a finite decimal is not treated as evidence that a real input is rational or that two tails are equal. The irrational case is kept separate from the terminating rational case.
Definitions
Definition 11.1.1
(The continued-fraction algorithm)
Start with , set , and, unless is an integer, put
The numbers are partial quotients, and the are complete quotients. We have and for . The finite expression obtained by nested reciprocation is the th convergent, written .
For a rational input with , integer division of numerator by denominator gives the next remainder, and reciprocation exchanges its role with the previous denominator. Positive remainders strictly decrease, so the process terminates. Except for a one-term integer expansion, its final partial quotient is at least two. Conversely that final-entry convention makes the floor procedure recover every entry, proving uniqueness of the normalized finite expansion. Allowing a final one creates the alternative for .
An irrational input never terminates: integer subtraction and reciprocal preserve irrationality. Its finite convergents are defined without first assigning meaning to an infinite nested expression. Convergence to the original input will be proved below.
Definition 11.1.2
(Convergent recurrences and scaled error)
Use auxiliary initial values
and define and . The initial zero denominator is a recurrence seed, not a claimed rational approximation. For irrational , write . The quantity is the scaled error of a rational candidate ; its ordinary absolute error is for .
Theorems
Theorem 11.1.3
(Determinants, tails, and convergence)
The recurrences give the stated finite convergents, with positive denominators and relatively prime numerator and denominator. They satisfy
For irrational ,
In particular the convergents alternate around , tend to it, and satisfy .
Theorem 11.1.4
(Best scaled approximation and Legendre's criterion)
For irrational , integers with satisfy
If a reduced fraction , with , satisfies
then is a convergent. This is Legendre's sufficient criterion, not an assertion that every convergent satisfies that stronger error threshold.
Concept lensGeometric
Lattice points closest to a line
Plot each candidate as the lattice point . The scaled error is the vertical distance from that point to the line . Best scaled approximation therefore says: among lattice points with first coordinate , none lies vertically closer to the line than . The alternating signs say that successive convergent points lie on alternate sides of the line, and the determinant identity says that two neighboring ones span a parallelogram of area one containing no other lattice point.
Proof sketch or proof idea
Recurrence and unimodularity
Proof
(Matrix products, determinant and the exact error)
Substituting the nested fractions successively, or multiplying the matrices , gives
Right multiplication gives exactly the two recurrences, starting with . Each factor has determinant minus one, so the determinant identity follows. Any common divisor of divides that determinant and must be one. Denominators are positive, , and for because the previous denominator is then positive.
For the tail identity at , write . Replacing a tail by and collecting numerator and denominator gives the next identity by the recurrences. Subtracting and using the determinant yields the exact error formula. The sign alternates because its denominator is positive.
Since , the inner denominator exceeds . This gives the strict error bound. Also , so the positive denominator sequence grows without bound. The error therefore tends to zero, proving convergence rather than merely inferring it from a picture of alternating fractions. The possible equality does not affect this eventual growth.
Every competing pair has integer coordinates
Proof
(Opposite-sign coordinates in the convergent basis)
The two columns and have determinant one or minus one. Their matrix inverse has integer entries, so any pair can be written uniquely as
The corresponding errors satisfy , and the exact error formula gives opposite signs for the two deltas.
If , positivity of forces , giving the claimed bound. If , then would make a positive multiple of , forbidden by the denominator bound. The coefficients cannot both be positive, since then , nor both negative, since then . Hence they have opposite signs. Their two error contributions consequently have the same sign, so
This proves best scaled approximation for every allowed candidate, including ones not written in lowest terms. The denominator cutoff and the scaled-error definition are both essential to the statement.
An error smaller than the integer lattice permits
Proof
(A nonzero integer below one)
To prove Legendre's criterion, choose the largest index with ; unbounded growth and eventual strict increase ensure it exists and . Put . Best approximation gives .
If , the integer is nonzero, so . But
a contradiction. Thus the fractions agree. Lowest terms and positive denominators identify the candidate with the convergent's usual reduced form. The proof uses the impossibility of a nonzero integer with magnitude below one; it does not guess the partial quotients from a decimal expansion. The factor one half has a specific role: the competing pair contributes two error terms, and each is bounded using the same candidate error and a denominator no larger than its own. Strictness makes their sum smaller than one. At equality the integer contradiction disappears, so this proof does not establish an extra boundary case.
What a large partial quotient actually means
The tail lies strictly between its integer part and the next integer. Inserting both bounds into the exact error formula sharpens the estimate to
These are bounds on the actual error, not just its sign. Since , a large next partial quotient makes the current convergent unusually accurate relative to its squared denominator. The current convergent, rather than the next one, receives that benefit. For example, the entry sixteen after in the rational expansion of explains the closeness of to that rational input; the infinite irrational theorem itself still requires an irrational input.
There is also a precise dichotomy for irrational inputs. Suppose all partial quotients after the first satisfy , with . Because , the next denominator is at most . The lower bound above gives an error strictly greater than for every convergent. For a reduced fraction that is not a convergent, the contrapositive of Legendre's criterion gives an error at least , which is larger than . Thus every reduced rational satisfies a uniform lower bound of the form
Conversely, if the partial quotients are unbounded, then for any proposed positive constant choose a next partial quotient greater than . The upper error bound and give a convergent with error less than . No positive uniform constant of the displayed kind can then work. This proves, in both directions, that bounded partial quotients are equivalent to such a denominator-squared lower bound. Irrationals satisfying one are called badly approximable; the name concerns a uniform constant, not an absence of accurate approximations.
For , the proved repeated tail bounds every later partial quotient by two, so is a valid lower-bound constant. Its convergents still approach it arbitrarily closely as their denominators grow. The lower bound scales with the denominator, so it does not contradict convergence. No claim is made here that this simple constant is the largest possible one.
Proof X-ray
Why neighboring convergents control all competitors
Their determinant makes them an integer basis, not merely two nearby real numbers. The denominator restriction forces a competitor's basis coefficients to have opposite signs, which makes its two error terms reinforce rather than cancel. The converse criterion then squeezes a nonzero integer determinant below one. These are discrete obstructions underlying the approximation estimates.
Worked examples
Worked example 11.1.5
(A rational input and its final-entry convention)
Euclidean division gives , , and . Hence , with convergents . The final determinant is . The expansion has the same value but is not normalized. Neither finite expression is an infinite process needing a convergence theorem.
Worked example 11.1.6
(An exact repeating tail for the square root of two)
Since , its first complete quotient has integer part two and fractional part . The same complete quotient returns, so the expansion is . The first convergents are . Their errors alternate in sign by the theorem. The exact values for the first four are , motivating the quadratic equations studied next. Repetition was proved by an algebraic identity, not inferred from a repeated stretch of decimal digits.
Worked example 11.1.7
(Recognizing a convergent from an exact norm identity)
The integers ninety-nine and seventy satisfy . Therefore
Their gcd is one because a common divisor would have its square divide one. Legendre's criterion proves that is a convergent. The recurrence confirms it follows : numerator , denominator . The norm identity supplies an exact approximation certificate without numerical rounding.
Counterexample mode
Scaled error is not ordinary error
For , the convergent precedes , but has smaller ordinary error than : this comparison is equivalent to . There is no conflict with best scaled approximation. Its scaled errors satisfy , because . Both rational bounds follow by squaring positive numbers. The repair is to retain the factor in the theorem's error measure, rather than silently changing what is minimized.
Common mistakes
Common mistake
(A seed or a zero remainder is not a convergent)
A recurrence seed with denominator zero is not a convergent. The rational algorithm stops when the remainder is zero; reciprocating that remainder is undefined. A normalized rational expansion can have a second nonnormalized form, while an irrational input has an infinite floor algorithm.
Common mistake
(Legendre's bound is sufficient, not necessary)
The approximation theorem has an explicit denominator range and an explicit scaled error. Legendre's bound is sufficient for identifying a convergent, not necessary for all convergents.
Common mistake
(Finitely many repeated entries do not prove periodicity)
Exact equalities of quadratic tails can establish repetition; visual patterns in finitely many coefficients alone do not prove a general periodicity theorem. For example, the rational number shares its first five partial quotients with , yet its expansion stops. Every finite list of partial quotients is shared by infinitely many inputs.
Summary
Euclidean reciprocation produces convergents with a unimodular neighbor relation. Complete quotients give their exact signed errors and prove convergence. The same determinant supplies an integer basis that proves best scaled approximation and Legendre's converse criterion, preparing a rigorous route from quadratic equations to continued fractions.
Exercises
Quick check
(Compute the normalized continued fraction of and all its convergents.)
Run the Euclidean algorithm on and .
Solution · Answer
The divisions are , , , and . Thus the expansion is , and the recurrences give .
Quick check
(Prove that a reduced rational strictly between two neighboring convergents has denominator at least the sum of their denominators.)
Express in the integer basis formed by the two neighboring convergents.
Solution · Answer
Write in the unimodular integer basis. Taking determinants with each neighbor, strict betweenness and imply . Since they are integers, both are at least one, and . The mediant attains equality; its numerator and denominator are coprime because a common divisor would divide a neighbor determinant.
Quick check
(Prove by complete-quotient identities, and compute its first four convergents.)
Rationalize and track the complete quotients.
Solution · Answer
The first tail is , with integer part one. The next is , with integer part two, and its successor is the first tail again. Hence the repeating entries are one, two. The convergents are . The repeated first denominator one is allowed by the recurrence and does not prevent later strict growth.
Quick check
(Is the converse of Legendre's sufficient criterion true? Use the convergent of and prove the relevant error comparison exactly.)
Compare with by squaring positive numbers.
Solution · Answer
No. The preceding exercise proves is a convergent. But , since , so . The sufficient criterion fails for this genuine convergent. Its contrapositive therefore cannot be used to exclude all fractions whose error is at least that threshold.