Continued fractions turn repeated division into a numerical representation that exposes rational approximation, Diophantine structure and the solutions of Pell equations.
The same quotient sequence that appears in Euclid’s algorithm can be read as a continued fraction. For rational numbers the process terminates. For irrational numbers it continues forever. For square roots of nonsquares, something remarkable happens: after a finite beginning, the continued fraction becomes periodic.
Those periodic expansions are not merely descriptive. Their convergents generate exceptional rational approximations and, in the case of √D, solve equations such as x²−Dy²=1.
This is Guide 7 in the Bukit Timah Tutor Computational Number Theory series. Use the BTT Mathematics Hub for the wider Mathematics route.
Division algorithm → quotient sequence → continued fraction → convergents → Diophantine information.
1. From Euclid to continued fractions
Take the rational number 415/93. Euclid’s algorithm gives
415 = 4·93 + 43 93 = 2·43 + 7 43 = 6·7 + 1 7 = 7·1.
Rearranging each division produces
415/93 = 4 + 43/93
= 4 + 1/(93/43)
= 4 + 1/(2 + 1/(43/7))
= 4 + 1/(2 + 1/(6 + 1/7)).
We abbreviate this as
415/93=[4;2,6,7].
The Euclidean quotients have become the continued-fraction digits.
2. Simple continued fractions
A simple continued fraction has the form
[a0; a1,a2,a3,...] = a0 + 1/(a1 + 1/(a2 + 1/(a3 + ...))),
where a0 is an integer and a1,a2,… are positive integers.
Rational numbers have finite simple continued fractions. Irrational numbers have infinite expansions. This gives an exact representation system distinct from decimal notation.
3. Computing an irrational continued fraction
Start with a real number α. Set a0=floor(α), subtract a0, take the reciprocal of the fractional part, and repeat.
α0 = α a_k = floor(α_k) α_(k+1) = 1/(α_k − a_k).
For √2:
√2 = 1 + (√2−1) 1/(√2−1) = √2+1 = 2 + (√2−1).
The same fractional state returns immediately, so
√2=[1; overline{2}].
4. Convergents
Truncating a continued fraction gives rational approximations called convergents:
[a0] [a0;a1] [a0;a1,a2] ...
For √2=[1;2,2,2,…], the first convergents are
1, 3/2, 7/5, 17/12, 41/29, …
These fractions rapidly approach √2.
5. Recurrence for convergents
Let p_k/q_k be the k-th convergent. Initialise
p_(−2)=0, p_(−1)=1 q_(−2)=1, q_(−1)=0.
Then for k≥0,
p_k=a_k p_(k−1)+p_(k−2),
q_k=a_k q_(k−1)+q_(k−2).
This recurrence computes convergents without repeatedly rebuilding the nested fraction.
6. Worked convergents for 415/93
Using [4;2,6,7]:
4/1 9/2 58/13 415/93.
The final convergent recovers the exact rational input because the Euclidean continued fraction terminates.
7. Determinant identity
Consecutive convergents satisfy
p_k q_(k−1)−p_(k−1)q_k=(−1)^(k−1).
The determinant has absolute value 1. Therefore consecutive numerator-denominator pairs are coprime, and consecutive convergents are tightly interlaced.
The identity follows directly from the recurrence and is one of the main invariants of the convergent algorithm.
8. Why convergents are unusually good approximations
Continued-fraction convergents are among the best rational approximations available for a given denominator size. A standard estimate is
|α−p_k/q_k| < 1/q_k².
The exact theory is stronger, but the inequality already explains why denominators that are not especially large can produce striking accuracy.
For √2, 17/12 differs from √2 by less than 0.003, and 41/29 is closer still. The denominators grow while the approximation error falls roughly quadratically.
9. Best-approximation viewpoint
A convergent cannot generally be beaten by an arbitrary fraction with a substantially smaller denominator. This turns continued fractions into a systematic search for good rational approximations rather than a lucky guess.
That matters in Diophantine approximation, where the question is not whether an irrational can be approximated by rationals—it always can—but how efficiently denominator size can be converted into accuracy.
10. Continued fractions and linear fractional transformations
Each continued-fraction digit a corresponds to the matrix
[a 1] [1 0].
Multiplying these matrices accumulates convergent numerators and denominators. This is another representation of the same recurrence and connects continued fractions to matrix products and linear fractional transformations.
11. Quadratic irrationals become periodic
Lagrange’s theorem states that a real number has an eventually periodic simple continued fraction if and only if it is a quadratic irrational—an irrational root of a quadratic equation with integer coefficients.
Square roots √D for nonsquare positive integers D are therefore periodic after the initial term.
12. Algorithm for √D
A standard integer recurrence avoids floating-point drift. Let a0=floor(√D) and begin m0=0,d0=1,a0 as above. Then
m_(k+1) = d_k a_k − m_k d_(k+1) = (D − m_(k+1)^2)/d_k a_(k+1) = floor((a0 + m_(k+1))/d_(k+1)).
The state eventually repeats, revealing the period exactly with integer arithmetic.
13. Example: √13
The continued fraction is
√13=[3; overline{1,1,1,1,6}].
The period length is 5. Its convergents begin
3/1, 4/1, 7/2, 11/3, 18/5, 119/33, 137/38, 256/71, 393/109, 649/180, ...
The convergent 18/5 is especially notable because 18²−13·5²=324−325=−1. The convergent 649/180 satisfies 649²−13·180²=1.
14. Pell’s equation
For a positive nonsquare integer D, Pell’s equation is
x²−Dy²=1.
At first this looks like a two-variable quadratic Diophantine equation with infinitely many possible pairs. Continued fractions convert it into a finite periodic search for the fundamental solution.
15. Why convergents appear in Pell equations
If x²−Dy²=±1, then
|x²/y² − D| = 1/y².
So x/y is an exceptionally good rational approximation to √D. Continued fractions are exactly the mechanism that produces such approximations systematically.
16. Fundamental Pell solution from the period
Let L be the period length of √D.
- If L is even, the convergent ending at one full period gives the fundamental solution of x²−Dy²=1.
- If L is odd, two periods are needed for the +1 equation; one period instead yields a solution of x²−Dy²=−1.
For D=13, L=5 is odd. The one-period convergent 18/5 solves the negative Pell equation. Extending through the second period gives 649/180, the minimal positive solution of the +1 Pell equation.
17. Example: x²−2y²=1
Since √2=[1;overline{2}], the period length is 1, which is odd. The first convergent 1/1 gives 1²−2·1²=−1. The next convergent 3/2 gives
3²−2·2²=9−8=1.
Thus the fundamental positive solution is (3,2).
18. Generating all Pell solutions
If (x1,y1) is the fundamental positive solution of x²−Dy²=1, then all positive solutions are generated by powers
x_n+y_n√D=(x1+y1√D)^n.
For D=2, the fundamental unit is 3+2√2. Squaring gives 17+12√2, producing the next Pell solution (17,12); multiplying again gives 99+70√2, and so on.
19. Recurrence for Pell solutions
Multiplication by x1+y1√D gives an integer recurrence:
x_(n+1)=x1 x_n + D y1 y_n y_(n+1)=y1 x_n + x1 y_n.
The invariant x_n²−D y_n²=1 is preserved because norms multiply.
20. Negative Pell equation
The equation x²−Dy²=−1 is not always solvable. The continued-fraction period gives a clean criterion: for nonsquare D, the negative Pell equation has an integer solution exactly when the period length of √D is odd.
For D=13 the period length is 5, so a solution exists: 18²−13·5²=−1. For D=3, √3=[1;overline{1,2}] has even period length 2, and the negative Pell equation has no solution.
21. General equations x²−Dy²=N
Pell’s equation is the N=1 case of a wider family. For fixed D and N, solutions of x²−Dy²=N can interact with the unit solutions of the Pell equation. Once a particular solution is known, multiplying x+y√D by powers of a norm-1 unit can generate additional solutions.
The general theory is richer than the +1 case, but the same computational objects—continued fractions, convergents and units in quadratic rings—remain central.
22. Exact arithmetic matters
Period detection and Pell equations should not rely on approximate floating-point equality. The integer recurrences for √D avoid the danger that rounding makes two theoretically identical states appear different or two different states appear equal.
Computational number theory repeatedly prefers exact invariant-preserving arithmetic whenever the mathematical problem itself is exact.
23. Common mistakes
- Confusing decimal truncation with a convergent. Continued-fraction truncation is a different approximation process.
- Recomputing nested fractions from scratch. Use the p_k,q_k recurrence.
- Assuming every irrational continued fraction is periodic. Eventual periodicity characterises quadratic irrationals.
- Using floating point to detect exact period return. Prefer the integer m,d,a recurrence.
- Ignoring period parity in Pell’s equation. Odd and even periods locate the +1 and −1 solutions differently.
- Finding one Pell solution and stopping. The fundamental solution generates infinitely many positive solutions.
24. Practice set
- Find the continued fraction of 415/93.
- List its convergents.
- Find the first five convergents of √2.
- Verify the determinant identity for 7/5 and 3/2.
- Explain why convergents are useful for rational approximation.
- State the continued fraction of √13.
- Verify that 18²−13·5²=−1.
- Verify that 649²−13·180²=1.
- Find the fundamental solution of x²−2y²=1.
- Use it to generate the next solution.
- State the period-parity criterion for x²−Dy²=−1.
- Explain why exact integer recurrences are preferable for period detection.
25. Answers and checks
1. [4;2,6,7].
2. 4/1,9/2,58/13,415/93.
3. 1/1,3/2,7/5,17/12,41/29.
4. 7·2−3·5=14−15=−1.
5. They provide systematically exceptional approximations with error controlled by denominator size.
6. √13=[3;overline{1,1,1,1,6}].
7. 324−325=−1.
8. 649²=421201 and 13·180²=421200, leaving 1.
9. (3,2).
10. (3+2√2)²=17+12√2, so the next solution is (17,12).
11. The negative Pell equation is solvable exactly when the period length of √D is odd.
12. Exact state equality is required; floating-point rounding can corrupt period detection.
26. Continue the series
- Guide 5: Quadratic Residues, Symbols and Tonelli–Shanks
- Guide 6: Discrete Logarithms, Baby-Step Giant-Step and Pollard Rho
- Guide 7: Continued Fractions, Convergents and Pell Equations
- Guide 8: Elliptic Curves over Finite Fields and Point Arithmetic
Return to the Singapore Mathematics Hub for the complete public Mathematics estate.