Phase 19 - Lesson 19.12

Continued Fractions, Pell Equations, and Diophantine Approximation

The best rational approximations to a real number, the periodic expansion of a quadratic surd, and how that periodicity solves $x^2-Dy^2=1$.

⏱ 70 min● Advanced🔗 Prereqs: 19.1 Euclid; 19.4 exact arithmetic

↖ Phase 19 hub

Builds on: The continued-fraction algorithm IS the Euclidean algorithm of 19.1, run on a real number.
Leads to: 19.13 iterates the fundamental solution with matrix powers; the Euler Lab’s Number Theory path contains convergent, Pell and square-root-expansion problems.

Learning Objectives

Click a status chip to cycle: Not started → In progress → Studied → Practiced → Needs review → Mastered.

Compute the continued-fraction expansion of a rational and of a quadratic surd, and relate it to the Euclidean algorithm.
Derive the convergent recurrences $h_k=a_kh_{k-1}+h_{k-2}$, $k_k=a_kk_{k-1}+k_{k-2}$ and prove $h_kk_{k-1}-h_{k-1}k_k=(-1)^{k-1}$
State the best-approximation theorem and the error bound $|x-h_k/k_k|\lt 1/(k_kk_{k+1})$
Prove that the expansion of $\sqrt D$ is eventually periodic and use the period to find the fundamental solution of Pell’s equation.
Implement exact integer continued fractions and a Pell solver, verifying $x^2-Dy^2=1$ exactly.

Key Vocabulary

Continued fraction: $[a_0;a_1,a_2,\dots]=a_0+\cfrac{1}{a_1+\cfrac{1}{a_2+\cdots}}$ with $a_0\in\Z$ and $a_i\ge1$ integers.

Convergent: The rational $h_k/k_k$ obtained by truncating after $a_k$. Convergents alternate around $x$ and are in lowest terms automatically.

Best approximation: No fraction with denominator $\le k_k$ is closer to $x$ than $h_k/k_k$. Convergents are the ONLY such fractions.

Quadratic surd: $\sqrt D$ for non-square $D$; by Lagrange its continued fraction is eventually periodic: $[a_0;\overline{a_1,\dots,a_r}]$.

Pell’s equation: $x^2-Dy^2=1$ for non-square $D\gt 0$; always has infinitely many integer solutions, generated from a fundamental one.

Fundamental solution: The smallest positive solution $(x_1,y_1)$; all others come from $x_n+y_n\sqrt D=(x_1+y_1\sqrt D)^n$.

Intuition & Motivation

Intuition

Run the Euclidean algorithm on a real number instead of an integer pair: at each step, peel off the integer part and invert the remainder. The quotients you peel off are the continued fraction, and truncating gives the best possible rational approximations - better than anything you could get by rounding decimals. When the number is $\sqrt D$, the peeling process can only ever be in one of finitely many states, so it must cycle - and that cycle is exactly what hands you the solution to Pell’s equation.

The algorithm is Euclid

Given a real $x$, set $a_0=\lfloor x\rfloor$ and $x_1=1/(x-a_0)$; repeat. For a rational $p/q$ the quotients $a_i$ are precisely the quotients of the Euclidean algorithm on $(p,q)$, and the process terminates in $O(\log q)$ steps. For an irrational it never terminates.

Worked Example - Expand $\tfrac{415}{93}$ and $\sqrt{7}$

$415/93$: $415=4\cdot93+43$ so $a_0=4$; then $93/43$: $93=2\cdot43+7$, $a_1=2$; $43/7$: $43=6\cdot7+1$, $a_2=6$; $7/1$: $a_3=7$. So $415/93=[4;2,6,7]$ - the very quotients Euclid produces.

Convergents: $4,\ 4+\tfrac12=\tfrac92,\ [4;2,6]=\tfrac{58}{13},\ [4;2,6,7]=\tfrac{415}{93}$. Each is already in lowest terms.

$\sqrt7\approx2.6457513$: $a_0=2$, and $x_1=1/(\sqrt7-2)=(\sqrt7+2)/3\approx1.5486$ so $a_1=1$.

Continuing in exact surd arithmetic (never decimals!): $\sqrt7=[2;\overline{1,1,1,4}]$ - period 4.

Convergents of $\sqrt7$: $2/1,\ 3/1,\ 5/2,\ 8/3,\ 37/14,\ 45/17,\dots$ Check $8/3$: $8^2-7\cdot3^2=64-63=1$. That is a Pell solution, appearing exactly at the end of the first period.

The pattern is not a coincidence - it is the theorem below.

Convergent recurrences

Theorem - Convergents

With $h_{-1}=1,\ h_{-2}=0,\ k_{-1}=0,\ k_{-2}=1$, define

\[h_k=a_kh_{k-1}+h_{k-2},\qquad k_k=a_kk_{k-1}+k_{k-2}.\] (19.26)

Then $[a_0;a_1,\dots,a_k]=h_k/k_k$, and

\[h_k k_{k-1}-h_{k-1}k_k=(-1)^{k-1}\qquad\Longrightarrow\qquad \gcd(h_k,k_k)=1 .\] (19.27)

Proof

Induct on $k$. The determinant identity (19.27) holds at the base, and each step multiplies the matrix $\begin{pmatrix}h_k&h_{k-1}\\ k_k&k_{k-1}\end{pmatrix}$ on the right by $\begin{pmatrix}a_{k+1}&1\\1&0\end{pmatrix}$, whose determinant is $-1$. So the determinant alternates sign. Since any common divisor of $h_k,k_k$ divides $(-1)^{k-1}$, the convergent is automatically in lowest terms. Note this is the same $2\times2$ matrix machinery as 19.13 - a continued fraction is a product of integer matrices.

Theorem - Approximation quality

Dividing (19.27) by $k_kk_{k-1}$ gives $\left|\frac{h_k}{k_k}-\frac{h_{k-1}}{k_{k-1}}\right|=\frac{1}{k_kk_{k-1}}$, and since $x$ lies between consecutive convergents,

\[\left|x-\frac{h_k}{k_k}\right|\lt \frac{1}{k_k k_{k+1}}\le\frac{1}{k_k^2}.\] (19.28)

Moreover (Lagrange) the convergents are the only fractions $p/q$ with $|x-p/q|\lt 1/(2q^2)$: they are the best rational approximations, full stop. That is why $\pi\approx355/113$ (a convergent) is accurate to $2.7\times10^{-7}$ with a 3-digit denominator, while the decimal 3.1416 needs a denominator of 10 000 to do worse.

Pell’s equation

Theorem - Pell via continued fractions

Let $D\gt 0$ be a non-square and let $\sqrt D=[a_0;\overline{a_1,\dots,a_r}]$ have period $r$. Then the fundamental solution of $x^2-Dy^2=1$ is $(x_1,y_1)=(h_{r-1},k_{r-1})$ when $r$ is even, and $(h_{2r-1},k_{2r-1})$ when $r$ is odd. Every solution is then $x_n+y_n\sqrt D=(x_1+y_1\sqrt D)^n$, $n\ge1$.

The key mechanism: the convergents satisfy $h_k^2-Dk_k^2=(-1)^{k+1}Q_{k+1}$ for the surd-algorithm quantities $Q$, and at the end of a period $Q=1$. Whether the sign is $+1$ or $-1$ depends on the parity of the period - hence the case split. Solutions grow explosively: for $D=61$ the fundamental solution is $x=1{,}766{,}319{,}049,\ y=226{,}153{,}980$, which is why float-based search is hopeless and exact integer arithmetic (19.4) is mandatory.

Key Idea

Pell is where three earlier lessons converge: Euclid (19.1) gives the algorithm, exact arithmetic (19.4) makes it trustworthy, and matrix exponentiation (19.13) generates the $n$-th solution from the first in $O(\log n)$ steps rather than $n$.

Coding workbench

Convergent-based approximation, square-root expansions, and Pell-type Diophantine equations are a recognisable cluster in the Euler Lab’s Number Theory path. They are also the clearest demonstration in this phase that the ‘obvious’ float method does not merely lose accuracy - it cannot even represent the answer.

Common Mistakes to Avoid

Expanding $\sqrt D$ with floating point. The quotients $a_i$ go wrong after a few dozen terms and the period is detected in the wrong place. Use the exact $(m,d,a)$ recurrence.
Using int(math.sqrt(D)) for $a_0$ instead of math.isqrt(D) - wrong for large $D$ (19.4).
Forgetting the parity rule in Pell: for an odd period you must go around TWICE ($2r-1$), or you will find $x^2-Dy^2=-1$ instead of $+1$.
Assuming Pell has a solution for square $D$. It does not: $x^2-4y^2=(x-2y)(x+2y)=1$ forces the trivial $y=0$.
Storing convergents as floats to ‘check’ them. Verify $x^2-Dy^2=1$ in exact integers; that is a proof, and a float check is not.

Quant Practitioner Tips

The period of $\sqrt D$ always ends with the term $2a_0$ - the cheapest and most reliable termination test.
Convergents alternate: even-indexed ones lie below $x$, odd-indexed above. Handy for two-sided bounds.
$[a_0;a_1,\dots]$ with all $a_i=1$ is the golden ratio - the ‘most irrational’ number, i.e. the hardest to approximate (19.28) with small denominators. That is why $\varphi$ shows up in worst-case analyses like Euclid’s.
Once you have the fundamental solution, all further Pell solutions come from powers of $x_1+y_1\sqrt D$ - and those powers are a $2\times2$ matrix power (19.13), so the $n$-th solution costs $O(\log n)$.

Practice this in the Euler Lab

Computational problems that exercise exactly this technique. Each opens in the Euler Lab with a Python workbench, a progressive hint ladder, and answer checking. Tier A/B run at full scale in the browser.

Warm-up:
#57 Square Root Convergents (5%, tier A) #65 Convergents of $e$ (6%, tier A) #64 Odd Period Square Roots (8%, tier A) #108 Diophantine Reciprocals I (12%, tier B)

Applied:
#66 Diophantine Equation (29%, tier B) #946 Continued Fraction Fraction (31%, tier C) #764 Asymmetric Diophantine Equation (35%, tier C)

Challenge:
#157 Base-10 Diophantine Reciprocal (42%, tier C) #454 Diophantine Reciprocals III (54%, tier C)

13 Project Euler problems in total are mapped to this lesson. Open the Euler Lab to filter them all.

Knowledge Check

Q1 Easy

The continued-fraction expansion of a rational $p/q$ is:

Infinite

Exactly the sequence of quotients produced by the Euclidean algorithm on $(p,q)$

Always periodic

Only defined for $p\lt q$

Q2 Hard

Why are convergents the best rational approximations?

They have the smallest numerators

Because $|x-h_k/k_k|\lt 1/(k_kk_{k+1})$, and no fraction with a denominator $\le k_k$ gets closer

Because they are in lowest terms

Because they alternate

Q3 Medium

For $D=61$ the fundamental Pell solution has $x=1{,}766{,}319{,}049$. This shows that:

Pell equations have no small solutions

Fundamental solutions can be enormous, so brute-force search over $y$ and float arithmetic both fail

61 is prime

The continued fraction of $\sqrt{61}$ is infinite in an unusual way

Practical Exercise

(a) Compute the continued fraction and the first five convergents of $\sqrt{2}$, and verify which of them solve $x^2-2y^2=\pm1$. (b) Prove that consecutive convergents satisfy $h_kk_{k-1}-h_{k-1}k_k=(-1)^{k-1}$ and deduce that every convergent is in lowest terms. (c) Explain why the continued fraction of a quadratic surd must be eventually periodic (a pigeonhole argument).

▶ Show full solution

(a) $\sqrt2=[1;\overline{2}]$ (period 1, all quotients 2 after the first). Convergents via (19.26): $1/1,\ 3/2,\ 7/5,\ 17/12,\ 41/29$. Test $h^2-2k^2$: $1-2=-1$; $9-8=+1$; $49-50=-1$; $289-288=+1$; $1681-1682=-1$. So the values alternate $\mp1$, and the solutions of $x^2-2y^2=1$ are the ODD-indexed convergents $(3,2),(17,12),\dots$. This is the odd-period case of the theorem: period $r=1$ is odd, so the fundamental solution is at index $2r-1=1$, i.e. $(3,2))$. ✓

(b) Induction. Base: $h_0k_{-1}-h_{-1}k_0=a_0\cdot0-1\cdot1=-1=(-1)^{-1}$. Step: using (19.26), $h_{k}k_{k-1}-h_{k-1}k_{k}=(a_kh_{k-1}+h_{k-2})k_{k-1}-h_{k-1}(a_kk_{k-1}+k_{k-2})=h_{k-2}k_{k-1}-h_{k-1}k_{k-2}=-(h_{k-1}k_{k-2}-h_{k-2}k_{k-1})$, so the quantity flips sign each step, giving $(-1)^{k-1}$. Any common divisor $d$ of $h_k$ and $k_k$ divides the left side, hence divides $\pm1$, so $d=1$. □

(c) Run the exact surd recurrence: the state is $(m,d)$ with the current value $(\sqrt D+m)/d$. One shows by induction that $d\mid D-m^2$ and that $0\lt m\lt \sqrt D$, $0\lt d\lt 2\sqrt D$ for all sufficiently large indices. So the state lives in a FINITE set (at most $2D$ pairs). By pigeonhole some state must repeat; and because the next state is a deterministic function of the current one, from that point the sequence cycles forever. That is Lagrange’s theorem, and the bound also tells you the period is $O(\sqrt D\log D)$ - short enough to compute.

After the reveal, answer for yourself: The pigeonhole argument in (c) bounds the period without ever computing one. Where else in this phase did a finiteness argument replace a computation?

Lesson Summary

The continued-fraction algorithm is Euclid run on a real number, and truncating it gives the convergents $h_k/k_k$ - provably the best rational approximations, with $|x-h_k/k_k|\lt 1/k_k^2$ and automatic lowest terms (from the determinant identity $h_kk_{k-1}-h_{k-1}k_k=(-1)^{k-1}$). For a non-square $D$ the expansion of $\sqrt D$ is eventually periodic (pigeonhole on a finite exact state), and the convergent at the end of the period - index $r-1$ for even period, $2r-1$ for odd - is the fundamental solution of Pell’s $x^2-Dy^2=1$.

Retrieval Practice

Close the lesson and answer from memory before checking. This is deliberate, effortful recall - the single highest-yield study action.

▶ Show retrieval prompts & answers

Q: State the convergent recurrence and the determinant identity it satisfies.
A: $h_k=a_kh_{k-1}+h_{k-2}$, $k_k=a_kk_{k-1}+k_{k-2}$; and $h_kk_{k-1}-h_{k-1}k_k=(-1)^{k-1}$, which forces $\gcd(h_k,k_k)=1$ and gives the error bound $|x-h_k/k_k|\lt 1/(k_kk_{k+1})$.

Q: How do you get the fundamental solution of $x^2-Dy^2=1$ from the CF of $\sqrt D$?
A: Expand $\sqrt D=[a_0;\overline{a_1,\dots,a_r}]$ exactly (integer $(m,d,a)$ recurrence, period ends at $a=2a_0$). Take the convergent at index $r-1$ if $r$ is even, else $2r-1$. Verify $x^2-Dy^2=1$ in exact integers.

Completion Checklist

I can explain the core ideas in my own words
I worked the derivations/examples by hand
I completed the interactive workbench(es)
I passed the knowledge check

Confidence / mastery rating

Personal notes

Source References

This lesson synthesizes and paraphrases concepts from the sources below. No copyrighted text, problem sets, or solutions are reproduced. Return to the originals for full depth.

Calculus, Vol. I (Tom Apostol, 2nd ed., 1967) foundational - Ch. 10 (sequences & series) - Limits, monotone approximation and the rigorous handling of infinite processes - the analytic backing for convergence of the convergents.
Numerical Linear Algebra (Trefethen & Bau, SIAM, 1997) foundational - Lectures 13–15 - Why an exact integer recurrence beats a floating-point one when the quantity of interest is a discrete decision (here, the partial quotients and the period).
The Pragmatic Programmer (Thomas & Hunt, 2nd/20th Anniv. ed., 2019) current - Ch. 7 - Verify with an invariant, not an eyeball: any Pell candidate must satisfy $x^2-Dy^2=1$ in exact integers - a one-line, unfoolable test.

← 19.11 Next: 19.13 →