Back to the on-screen lesson ·
Euclid's quotients read as an expansion, the fractions they build, and why those are the best approximations that exist.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to expand a rational number as a continued fraction and recognise its partial quotients as Euclid's quotients, build the convergents with the two-term recurrence, use the determinant identity to check them and to read off a Bézout identity, and say why the convergents alternate around the value and are the best approximations at their size.
Lesson 2 ran Euclid's algorithm and kept the last non-zero remainder. Lesson 3 went back up the run and kept the Bézout coefficients. Both threw the quotients away.
Those quotients carry the rest of the information. Written in the right shape they express the original fraction exactly, and truncating that expression gives a sequence of simpler fractions closing in on it — which turn out to be the best approximations that exist at their size. One algorithm, three different things read off it.
A continued fraction is an expression $$a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{\ddots}}}$$ written compactly as $[a_0; a_1, a_2, \ldots]$. The $a_i$ are the partial quotients; all but $a_0$ are positive integers.
The $k$-th convergent $p_k/q_k$ is what you get by stopping after $a_k$.
A rational number has a finite expansion; an irrational number has an infinite one. A periodic expansion — one that eventually repeats — belongs exactly to the quadratic irrationals, which is the next lesson.
The expansion. Take the whole part, subtract it, invert what is left, and repeat. For a rational number the successive denominators are exactly the remainders of Euclid's algorithm, which strictly decrease, so the process stops. For an irrational one it never stops.
The recurrence. With $p_{-1} = 1$, $p_{-2} = 0$, $q_{-1} = 0$, $q_{-2} = 1$: $$p_k = a_k p_{k-1} + p_{k-2}, \qquad q_k = a_k q_{k-1} + q_{k-2}.$$ Numerators and denominators obey the same rule and differ only in how they start.
The determinant identity. $$p_k q_{k-1} - p_{k-1}q_k = (-1)^{k-1}.$$ Three consequences, all used constantly:
Alternation and approximation. The convergents alternate around the value — odd ones below, even ones above — and each is closer than its predecessor, so consecutive convergents bracket the target. The error satisfies $$\left|x - \frac{p_k}{q_k}\right| < \frac{1}{q_kq_{k+1}} \le \frac{1}{q_k^{2}}.$$
Best approximation. More than close: no fraction with denominator at most $q_k$ is closer to $x$ than $p_k/q_k$ is. That is why convergents rather than decimals are the right answer to approximate this number simply, and why $355/113$ agrees with $\pi$ to six decimal places while having only a three-digit denominator.
Another way: steps
Another way: example
$\frac{43}{19} = [2; 3, 1, 4]$: $43 = 2 \cdot 19 + 5$, $19 = 3 \cdot 5 + 4$, $5 = 1 \cdot 4 + 1$, $4 = 4 \cdot 1$. Convergents: $2/1$, $7/3$, $9/4$, $43/19$. Check the identity: $7 \cdot 1 - 2 \cdot 3 = 1$, and $9 \cdot 3 - 7 \cdot 4 = -1$.
Decimals approximate by fixing the denominator in advance — tenths, then hundredths — and that is wasteful. $\pi \approx 3.14159$ costs a denominator of $100\,000$ for five decimal places. The convergent $355/113$ does better with a denominator of $113$.
The reason is that a continued fraction spends denominator only where it buys accuracy. A large partial quotient means the previous convergent was already very good: truncating just before it leaves a small error, because the correction being discarded is $1/a_k$ times something. $\pi = [3; 7, 15, 1, 292, \ldots]$, and the $292$ is why $355/113 = [3; 7, 15, 1]$ is so extraordinarily good — the next correction is tiny.
Contrast the golden ratio $\varphi = [1; 1, 1, 1, \ldots]$, every partial quotient as small as it can be. Its convergents are ratios of consecutive Fibonacci numbers, and they converge as slowly as any number's can. That is what the most irrational number means: not that it is somehow more irrational, but that its rational approximations are the worst possible. Hurwitz's theorem makes it exact — $|x - p/q| < 1/(\sqrt5 q^{2})$ has infinitely many solutions for every irrational $x$, and the constant $\sqrt5$ cannot be improved because of $\varphi$.
The same theory is also where irrationality proofs come from. An expansion that does not terminate is an irrational number, by definition; an expansion that is eventually periodic is a quadratic irrational, which is Lagrange's theorem and the subject of the next lesson.
And it has a use with no approximation in it at all. The determinant identity $p_kq_{k-1} - p_{k-1}q_k = \pm 1$ is a Bézout identity, so expanding $a/n$ as a continued fraction and reading off the last-but-one convergent gives the inverse of $a$ modulo $n$ — the extended Euclidean algorithm, arrived at from the other direction.
Rounding instead of taking the whole part. The expansion takes the floor. Rounding up produces a different and non-standard expansion with negative terms.
Losing the alternation. The convergents do not approach from one side. They alternate, which is what lets two consecutive ones bracket the value and bound the error.
Applying the recurrence to the wrong pair. Each step uses the two previous convergents, not the previous one and the original fraction.
Expecting the expansion to be unique. Every rational has exactly two: $[a_0; \ldots, a_k]$ with $a_k > 1$ equals $[a_0; \ldots, a_k - 1, 1]$. The convention is to forbid a final $1$.
Thinking a good approximation must come from a convergent's neighbourhood. The theorem is sharper and simpler than that: every best approximation is a convergent. There is nothing else to look for.
$\frac{87}{32}$: whole part $2$, leaving $23/32$; invert to $32/23$, whole part $1$, leaving $9/23$; invert to $23/9$, whole part $2$, leaving $5/9$; invert to $9/5$, whole part $1$, leaving $4/5$; invert to $5/4$, whole part $1$, leaving $1/4$; invert to $4$. So $[2; 1, 2, 1, 1, 4]$.
Whole part, subtract, invert, repeat.
Convergents by the recurrence: $2/1$, $3/1$, $8/3$, $11/4$, $19/7$, $87/32$.
Two rows at a time, numerators and denominators alike.
Check the determinant: $3 \cdot 1 - 2 \cdot 1 = 1$, $8 \cdot 1 - 3 \cdot 3 = -1$, $11 \cdot 3 - 8 \cdot 4 = 1$. Alternating $\pm 1$, as it must.
The identity is the cheapest available check.
Find $19^{-1}$ modulo $32$. Expand the modulus over the residue: $32 = 1 \cdot 19 + 13$, $19 = 1 \cdot 13 + 6$, $13 = 2 \cdot 6 + 1$, $6 = 6 \cdot 1$, so $32/19 = [1; 1, 2, 6]$.
Expand the modulus over the residue.
Convergents by the recurrence: $1/1$, $2/1$, $5/3$, $32/19$. The last-but-one is $5/3$.
Only the last-but-one is needed.
The determinant identity gives $32 \cdot 3 - 19 \cdot 5 = 96 - 95 = 1$, so $-19 \cdot 5 \equiv 1 \pmod{32}$ and $19^{-1} \equiv -5 \equiv 27$. Check: $19 \cdot 27 = 513 = 16 \cdot 32 + 1$.
A Bézout identity, read off a convergent.
$50 = 2 \cdot 17 + 16$, $17 = 1 \cdot 16 + 1$, $16 = 16 \cdot 1$. So the expansion is $[2; 1, 16]$.
The quotients are Euclid's, in order.
Convergents: $2/1$, then $(1 \cdot 2 + 1)/(1 \cdot 1 + 0) = 3/1$, then $(16 \cdot 3 + 2)/(16 \cdot 1 + 1) = 50/17$.
The recurrence, twice.
The large final quotient $16$ says $3/1$ was already a good approximation: $50/17 \approx 2.94$, and $3$ is within $0.06$.
The continued fraction of $163/38$ has partial quotients $4$, $3$, $2$, $5$. Give the numerator and denominator of each of the first three convergents.
| Numerator | Denominator | |
|---|---|---|
| First convergent | ||
| Second convergent | ||
| Third convergent |
Expand $41/35$ as a continued fraction. What is its second partial quotient?
Answer:
Put the four steps of expanding $24/13$ as a continued fraction into the order they are carried out.
Number the steps in order (write the number in the box):
The continued fraction of $59/21$ begins with partial quotients $2$ and $1$. Give the numerator and denominator of its second convergent.
numerator a, denominator c
For $183/41$, with partial quotients $4$, $2$, $6$, $3$, what is the denominator of the third convergent?
Answer:
The convergents of $59/21$ are $2/1$, $3/1$ and $14/5$. Match each to whether it lies above or below $59/21$.
| below the value | above the value | |
|---|---|---|
| $2/1$ | ||
| $3/1$ | ||
| $14/5$ |
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
The continued fraction of $31/14$ has partial quotients $2$, $4$, $1$, $2$. Give the numerator and denominator of each of the first three convergents.
| Numerator | Denominator | |
|---|---|---|
| First convergent | ||
| Second convergent | ||
| Third convergent |
You can expand a fraction and compute its convergents, and check them with the determinant identity. Say in your own words why a large partial quotient means the previous convergent was already good. Next: what an expansion that repeats for ever is telling you.
9. Your turn: expand $\frac{50}{17}$ and give its convergents, step 3