Continued Fractions Reference Cheat Sheet

Key Facts

• A simple continued fraction has the form $[a_0; a_1, a_2, a_3, \ldots] = a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{a_3 + \cdots}}}$, where $a_0$ is an integer and $a_i$ for $i \ge 1$ are positive integers.
• To convert a rational number to a finite continued fraction, repeatedly divide using the Euclidean algorithm: $x = a_0 + \frac{1}{x_1}$, then $x_1 = a_1 + \frac{1}{x_2}$, and continue until the remainder is $0$.
• The $n$th convergent of $[a_0; a_1, \ldots, a_n]$ is $\frac{p_n}{q_n}$, a rational approximation formed by stopping the continued fraction after $a_n$.
• The convergent numerators and denominators satisfy $p_n = a_n p_{n-1} + p_{n-2}$ and $q_n = a_n q_{n-1} + q_{n-2}$.
• Useful starting values for convergents are $p_{-2} = 0$, $p_{-1} = 1$, $q_{-2} = 1$, and $q_{-1} = 0$.
• Consecutive convergents obey $p_n q_{n-1} - p_{n-1} q_n = (-1)^{n-1}$, so each convergent $\frac{p_n}{q_n}$ is already in lowest terms.
• For an irrational number $x$, the convergents usually alternate around $x$, and the error satisfies $\left|x - \frac{p_n}{q_n}\right| < \frac{1}{q_n q_{n+1}}$.
• A quadratic irrational number has an eventually periodic continued fraction, such as $\sqrt{2} = [1; \overline{2}]$.

Vocabulary

Continued fraction

A continued fraction is a number representation built from an integer plus the reciprocal of another expression of the same type.

Simple continued fraction

A simple continued fraction is a continued fraction $[a_0; a_1, a_2, \ldots]$ whose terms after $a_0$ are positive integers.

Partial quotient

A partial quotient is one of the integers $a_0, a_1, a_2, \ldots$ in a continued fraction.

Convergent

A convergent is a rational approximation $\frac{p_n}{q_n}$ found by stopping a continued fraction after finitely many partial quotients.

Periodic continued fraction

A periodic continued fraction is a continued fraction whose partial quotients repeat in a pattern, written with an overline such as $[1; \overline{2}]$.

Euclidean algorithm

The Euclidean algorithm is the repeated division process used to find greatest common divisors and finite continued fractions for rational numbers.