Continued Fractions of Square Roots

A rational number has a finite continued fraction. An irrational number does not: the algorithm runs forever. For square roots something remarkable happens: the partial quotients repeat. Finding the pattern needs exact arithmetic with radicals, the kind practiced in Algebra 1.

The algorithm. Start with $x_0 = x$. At each step take the whole part $a_k = \lfloor x_k \rfloor$, then flip what is left: $x_{k+1} = \dfrac{1}{x_k - a_k}$. Then $x = [a_0; a_1, a_2, \dots]$.

Theorem (Lagrange). If $d$ is a positive integer that is not a perfect square, the continued fraction of $\sqrt{d}$ is periodic: $$\sqrt{d} = [a_0; \overline{a_1, a_2, \dots, a_{r-1}, 2a_0}],$$ where the bar marks the block that repeats forever, and the block always ends with $2a_0$.

Why it works

Each $x_k$ can be written exactly as $\dfrac{\sqrt{d} + m}{c}$ with whole numbers $m$ and $c$, by rationalizing the denominator each time. One can show $0 \le m < \sqrt{d}$ and $0 < c < 2\sqrt{d}$, so there are only finitely many possible pairs $(m, c)$. Sooner or later a pair repeats, and from then on every step repeats too. Rounding to decimals destroys exactly this information, which is why the computation must stay exact.

Worked example: The continued fraction of √7

Find the continued fraction of $\sqrt{7}$.

$2 < \sqrt{7} < 3$, so $a_0 = 2$ and $x_1 = \dfrac{1}{\sqrt{7} - 2} = \dfrac{\sqrt{7} + 2}{3} \approx 1.55$. So $a_1 = 1$.
$x_2 = \dfrac{1}{x_1 - 1} = \dfrac{3}{\sqrt{7} - 1} = \dfrac{3(\sqrt{7} + 1)}{6} = \dfrac{\sqrt{7} + 1}{2} \approx 1.82$. So $a_2 = 1$.
$x_3 = \dfrac{1}{x_2 - 1} = \dfrac{2}{\sqrt{7} - 1} = \dfrac{\sqrt{7} + 1}{3} \approx 1.22$. So $a_3 = 1$.
$x_4 = \dfrac{1}{x_3 - 1} = \dfrac{3}{\sqrt{7} - 2} = \sqrt{7} + 2 \approx 4.65$. So $a_4 = 4 = 2a_0$, and $x_4 - 4 = \sqrt{7} - 2$, where we started.

Answer: $\sqrt{7} = [2; \overline{1, 1, 1, 4}]$.

The $\sqrt{7} \times 1$ rectangle cut into squares never comes out even, but the counts settle into the block 1, 1, 1, 4. The last column, $p^{2} - 7q^{2}$, is always small: a hint of Pell's equation.

Worked example: The simplest case

Find the continued fraction of $\sqrt{2}$.

$a_0 = 1$, and $x_1 = \dfrac{1}{\sqrt{2} - 1} = \sqrt{2} + 1 \approx 2.41$, so $a_1 = 2$.
$x_1 - 2 = \sqrt{2} - 1$, the same leftover as before, so every later quotient is 2.

Answer: $\sqrt{2} = [1; \overline{2}]$.

Worked example: Best approximations

Find the convergents of $\sqrt{7} = [2; 1, 1, 1, 4, \dots]$ up to $\frac{p_4}{q_4}$.

With the recurrence: $\frac{2}{1}, \frac{3}{1}, \frac{5}{2}, \frac{8}{3}, \frac{37}{14}$.
$\frac{37}{14} \approx 2.642857$, while $\sqrt{7} \approx 2.645751$. No fraction with denominator at most 14 comes closer.
Notice $8^{2} - 7 \cdot 3^{2} = 64 - 63 = 1$, a whole-number solution of $x^{2} - 7y^{2} = 1$.

Answer: $\frac{2}{1}, \frac{3}{1}, \frac{5}{2}, \frac{8}{3}, \frac{37}{14}$.

Common mistake

Switching to rounded decimals. With $\sqrt{7} \approx 2.6458$, a few flips amplify the rounding error until the quotients come out wrong, and the repeating pattern is never seen. Keep exact forms such as $\dfrac{1}{\sqrt{7} - 2}$ and rationalize: multiply top and bottom by $\sqrt{7} + 2$.

Key idea

For $\sqrt{d}$, flip and take whole parts with exact radicals: $\sqrt{d} = [a_0; \overline{a_1, \dots, 2a_0}]$ is periodic, and its convergents are the best rational approximations to $\sqrt{d}$.

Continued Fractions of Square Roots

Practice

Builds on

Leads to

Sources and further reading