Introduction to Continued Fractions

A continued fraction represents a real number as a nested tower of integer parts and reciprocals instead of a single numerator and denominator. This alternative representation turns out to encode, in an unusually transparent way, both whether a number is rational and, if it is irrational, exactly how well it can be approximated by fractions.

The Continued Fraction Algorithm

A simple continued fraction is an expression of the form

\[x=a_0+\cfrac{1}{a_1+\cfrac{1}{a_2+\cfrac{1}{a_3+\ddots}}},\]

where \(a_0\) is an integer and every subsequent \(a_i\) is a positive integer. It is written compactly as \(x=[a_0;a_1,a_2,\ldots]\).

Every real number \(x\) has such an expansion, produced by peeling off an integer part and inverting the remainder, over and over:

\[ x_0=x, \qquad a_n=\lfloor x_n\rfloor, \qquad x_{n+1}=\frac{1}{x_n-a_n}. \]

Here \(\lfloor x_n\rfloor\) denotes the floor of \(x_n\), the largest integer not exceeding it. The process stops if some \(x_n\) is itself an integer, since then \(x_n-a_n=0\) and there is nothing left to invert.

Example. For \(x=\frac{47}{17}\):

\[ \begin{aligned} x_0&=\tfrac{47}{17}=2.7\overline{6470588235294117}, & a_0&=2,\\ x_1&=\frac{1}{47/17-2}=\frac{17}{13}=1.307\ldots, & a_1&=1,\\ x_2&=\frac{1}{17/13-1}=\frac{13}{4}=3.25, & a_2&=3,\\ x_3&=\frac{1}{13/4-3}=4, & a_3&=4, \end{aligned} \]

and \(x_3\) is an integer, so the process stops. Hence \(\frac{47}{17}=[2;1,3,4]\), which unfolds to

\[\frac{47}{17}=2+\cfrac{1}{1+\cfrac{1}{3+\cfrac{1}{4}}}.\]

Why Rational Numbers Give Finite Expansions

Applying the algorithm above to a fraction \(\frac{p}{q}\) is, term for term, the Euclidean algorithm for \(\gcd(p,q)\): writing \(p=aq+r\) with \(0\le r<q\) gives the integer part \(a\) and leaves \(\frac{q}{r}\) as the next value to invert, exactly the next step of division with remainder. Since the Euclidean algorithm always terminates after finitely many steps, so does the continued fraction expansion of any rational number.

Conversely, unfolding a finite expression \([a_0;a_1,\ldots,a_n]\) from the innermost fraction outward only ever adds and inverts integers, which produces a rational number at every stage. So a real number has a finite continued fraction if and only if it is rational; an irrational number's expansion never terminates.

Convergents

Truncating \([a_0;a_1,a_2,\ldots]\) after \(n\) terms gives the \(n\)-th convergent \(\frac{p_n}{q_n}:=[a_0;a_1,\ldots,a_n]\), a rational number that approximates \(x\). Computing convergents directly by repeatedly unfolding the fraction is wasteful, since each new term requires redoing the whole computation. Instead, they satisfy a simple linear recurrence.

Set \(p_{-1}=1\), \(q_{-1}=0\), \(p_0=a_0\), \(q_0=1\), and for \(n\ge 1\):

\[p_n=a_np_{n-1}+p_{n-2},\qquad q_n=a_nq_{n-1}+q_{n-2}.\]

Proof. For \(n=0\) this matches the definition directly. Assume \([a_0;a_1,\ldots,a_{n-1},z]=\frac{zp_{n-1}+p_{n-2}}{zq_{n-1}+q_{n-2}}\) holds for an arbitrary real placeholder \(z\) in the last position (true for \(n=1\) by direct computation). Since \([a_0;\ldots,a_{n-1},a_n,z']=[a_0;\ldots,a_{n-1},a_n+\frac{1}{z'}]\), substituting \(z=a_n+\frac{1}{z'}\) gives

\[ [a_0;\ldots,a_n,z'] = \frac{(a_n+\frac1{z'})p_{n-1}+p_{n-2}}{(a_n+\frac1{z'})q_{n-1}+q_{n-2}} = \frac{z'(a_np_{n-1}+p_{n-2})+p_{n-1}}{z'(a_nq_{n-1}+q_{n-2})+q_{n-1}}, \]

which is exactly the claimed recurrence one step further, with \(p_{n-1}\) and \(q_{n-1}\) playing the role of the "previous" pair for the next step. Setting \(z'\) to an integer \(a_{n+1}\) recovers the ordinary convergent \(p_{n+1}/q_{n+1}\). \(\square\)

Example. Continuing \(\frac{47}{17}=[2;1,3,4]\):

confirming \(p_3/q_3=47/17\), the original fraction.

The Key Identity

The numerators and denominators satisfy

\[p_nq_{n-1}-p_{n-1}q_n=(-1)^{n-1}\]

for every \(n\ge 0\). Proof. For \(n=0\): \(p_0q_{-1}-p_{-1}q_0=a_0\cdot 0-1\cdot 1=-1=(-1)^{-1}\). Assuming the identity for \(n-1\),

\[ \begin{aligned} p_nq_{n-1}-p_{n-1}q_n &=(a_np_{n-1}+p_{n-2})q_{n-1}-p_{n-1}(a_nq_{n-1}+q_{n-2})\\ &=p_{n-2}q_{n-1}-p_{n-1}q_{n-2}\\ &=-\big(p_{n-1}q_{n-2}-p_{n-2}q_{n-1}\big)=-(-1)^{n-2}=(-1)^{n-1}.\quad\square \end{aligned} \]

Since any common divisor of \(p_n\) and \(q_n\) would have to divide \((-1)^{n-1}=\pm1\), every convergent \(\frac{p_n}{q_n}\) is automatically already in lowest terms.

Convergents Are the Best Rational Approximations

Dividing the key identity by \(q_nq_{n-2}\) and using the recurrence for \(p_n,q_n\) gives, after the same kind of computation,

\[\frac{p_n}{q_n}-\frac{p_{n-2}}{q_{n-2}}=\frac{(-1)^n a_n}{q_nq_{n-2}}.\]

Since \(a_n,q_n,q_{n-2}\) are all positive, this difference is positive for even \(n\) and negative for odd \(n\). So the even-indexed convergents \(\frac{p_0}{q_0}<\frac{p_2}{q_2}< \frac{p_4}{q_4}<\cdots\) increase, while the odd-indexed ones \(\frac{p_1}{q_1}>\frac{p_3}{q_3}>\cdots\) decrease, and both sequences converge to \(x\). Since consecutive convergents always have opposite parity, \(x\) is trapped strictly between any two consecutive convergents \(\frac{p_n}{q_n}\) and \(\frac{p_{n+1}}{q_{n+1}}\), which by the key identity are exactly \(\frac{1}{q_nq_{n+1}}\) apart. This gives the fundamental error bound

\[\left|x-\frac{p_n}{q_n}\right|<\frac{1}{q_nq_{n+1}}.\]

Because the denominators \(q_n\) grow at least as fast as the Fibonacci numbers (each \(q_n\ge q_{n-1}+q_{n-2}\)), this error shrinks quickly, and no fraction with a smaller denominator than \(q_n\) can approximate \(x\) more closely than \(\frac{p_n}{q_n}\) does — which is why the convergents of a continued fraction are called its best rational approximations.

Example. The continued fraction of \(\pi\) begins \([3;7,15,1,292,\ldots]\), with convergents \(3\), \(\frac{22}{7}=3.142857\ldots\), \(\frac{333}{106}\), and \(\frac{355}{113}=3.1415929\ldots\). The last of these is accurate to six decimal digits using a three-digit denominator, far better than a generic fraction of that size could achieve.

The Golden Ratio: the Hardest Number to Approximate

The golden ratio \(\varphi=\frac{1+\sqrt5}{2}\) is a root of \(x^2-x-1=0\), so it satisfies \(\varphi=1+\frac{1}{\varphi}\). Substituting this identity into itself over and over gives its continued fraction directly:

\[\varphi=1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{1+\ddots}}}=[1;1,1,1,\ldots].\]

Since every \(a_n=1\), the recurrence for the numerators becomes \(p_n=p_{n-1}+p_{n-2}\), the Fibonacci recurrence, with starting values \(p_{-1}=1\), \(p_0=1\); the denominators satisfy the same recurrence shifted by one index. So the convergents of \(\varphi\) are exactly ratios of consecutive Fibonacci numbers, \(\frac{p_n}{q_n}=\frac{F_{n+2}}{F_{n+1}}\).

The error bound above shows that a continued fraction with small partial quotients \(a_n\) approximates slowly, since the denominators \(q_n\) then grow as slowly as the recurrence allows. Taking every \(a_n=1\) is the smallest possible choice, and the Fibonacci numbers are precisely the slowest-growing sequence satisfying \(q_n=q_{n-1}+q_{n-2}\). This is the precise sense in which \(\varphi\) is the real number that is hardest to approximate well by fractions.

Continued Fractions of Quadratic Irrationals

A continued fraction is called eventually periodic if, from some point on, a block of terms repeats forever:

\[x=[a_0;a_1,\ldots,a_{m-1},\overline{a_m,\ldots,a_{m+k-1}}].\]

Lagrange's theorem states that a continued fraction is eventually periodic if and only if \(x\) is a quadratic irrational, an irrational root of a quadratic equation with integer coefficients.

The direction "periodic \(\Rightarrow\) quadratic irrational" is straightforward to see. Suppose the purely periodic tail is \(y=[\overline{a_m,\ldots,a_{m+k-1}}]\); since the block repeats, \(y\) equals itself with the same block prepended once more, so \(y=[a_m,\ldots,a_{m+k-1},y]\). Writing \(P/Q\) and \(P'/Q'\) for the last two convergents of the finite continued fraction \([a_m;\ldots,a_{m+k-1}]\), the convergent recurrence gives

\[y=\frac{Py+P'}{Qy+Q'}\quad\Longrightarrow\quad Qy^2+(Q'-P)y-P'=0,\]

a quadratic equation with integer coefficients, and \(y\) is irrational since an infinite purely periodic continued fraction cannot terminate. Then \(x=[a_0;\ldots,a_{m-1},y]=\frac{p_{m-1}y+p_{m-2}}{q_{m-1}y+q_{m-2}}\) is a ratio of integer linear expressions in \(y\), and substituting this relation into \(y\)'s quadratic equation shows \(x\) satisfies a quadratic equation with integer coefficients too. The converse — every quadratic irrational has an eventually periodic expansion — takes more work, and is proved in full generality below.

Quadratic Irrationals in Standard Form

Every quadratic irrational \(x\) can be written as \(x=\frac{u+\sqrt v}{w}\) with \(u,v,w\) integers, \(w\neq0\), \(v>0\) not a perfect square — this is just the quadratic formula applied to \(x\)'s defining equation. For the reduction algorithm below it is convenient to normalize this representation further.

Lemma. Every quadratic irrational can be written as

\[x=\frac{m+\sqrt d}{s},\qquad m,s,d\in\mathbb Z,\ s\neq0,\ d>0\text{ not a perfect square},\ s\mid d-m^2.\]

Proof. Starting from \(x=\frac{u+\sqrt v}{w}\), multiply numerator and denominator by \(|w|\):

\[x=\frac{u|w|+\sqrt{vw^2}}{w|w|}.\]

Set \(m=u|w|\), \(d=vw^2\), \(s=w|w|\); these are integers, \(s\neq0\), and \(d>0\) is not a perfect square, since multiplying \(v\) by the perfect square \(w^2\) does not change whether the product is itself a perfect square. Because \(d-m^2=(v-u^2)w^2\) and \(s=w|w|\) divides \(w^2\) (their ratio is \(\pm1\)), \(s\) also divides \((v-u^2)w^2=d-m^2\). \(\square\)

The Reduction Algorithm

Let \(x_0=\frac{m_0+\sqrt d}{s_0}\) be a quadratic irrational in standard form, so \(s_0\mid d-m_0^2\). Applying the continued fraction algorithm to \(x_0\) preserves this shape at every step: define, for \(k\ge0\),

\[a_k=\lfloor x_k\rfloor,\qquad m_{k+1}=a_ks_k-m_k,\qquad s_{k+1}=\frac{d-m_{k+1}^2}{s_k},\qquad x_{k+1}=\frac{m_{k+1}+\sqrt d}{s_{k+1}}.\]

This is exactly the ordinary continued fraction algorithm rewritten in the coordinates \((m_k,s_k)\): from \(x_k-a_k=\frac{\sqrt d-(a_ks_k-m_k)}{s_k}=\frac{\sqrt d-m_{k+1}}{s_k}\), rationalizing the reciprocal via \((\sqrt d-m_{k+1})(\sqrt d+m_{k+1})=d-m_{k+1}^2\) gives \(x_{k+1}=\frac1{x_k-a_k}=\frac{s_k(\sqrt d+m_{k+1})}{d-m_{k+1}^2}=\frac{m_{k+1}+\sqrt d}{s_{k+1}}\), which is exactly the formula above.

Every \(m_k,s_k\) is an integer, and \(s_k\mid d-m_{k+1}^2\), for all \(k\ge0\). This holds for \(k=0\) by the standard-form hypothesis. Assuming it for \(k\), \(m_{k+1}=a_ks_k-m_k\) is an integer, and \(s_{k+1}=(d-m_{k+1}^2)/s_k\) is an integer because \(s_k\mid d-m_{k+1}^2\) by assumption. For the next divisibility,

\[ \begin{aligned} d-m_{k+2}^2 &=d-(a_{k+1}s_{k+1}-m_{k+1})^2\\ &=(d-m_{k+1}^2)-s_{k+1}\big(a_{k+1}^2s_{k+1}-2a_{k+1}m_{k+1}\big)\\ &=s_{k+1}\Big(s_k-a_{k+1}^2s_{k+1}+2a_{k+1}m_{k+1}\Big), \end{aligned} \]

using \(d-m_{k+1}^2=s_ks_{k+1}\) in the last step. So \(s_{k+1}\mid d-m_{k+2}^2\), completing the induction. In particular \(s_k\neq0\) for every \(k\): if some \(s_{k+1}=0\), then \(s_ks_{k+1}=d-m_{k+1}^2=0\) would make \(d=m_{k+1}^2\) a perfect square, contradicting the hypothesis on \(d\). The whole computation therefore runs in exact integer arithmetic, with the square root only ever appearing symbolically through \(\sqrt d\).

Why the Algorithm Is Eventually Periodic

For \(x=\frac{m+\sqrt d}{s}\), write \(\overline x:=\frac{m-\sqrt d}{s}\) for its conjugate, obtained by flipping the sign in front of \(\sqrt d\). Since \(d\) is not a perfect square, replacing \(\sqrt d\) by \(-\sqrt d\) throughout is a field automorphism of \(\mathbb Q(\sqrt d)\) that fixes every rational number, and therefore commutes with addition, multiplication and division: \(\overline{x+y}=\overline x+\overline y\), \(\overline{xy}=\overline x\,\overline y\), and \(\overline{x/y}=\overline x/\overline y\).

Recall from the convergent recurrence that peeling off the algorithm \(n\) times leaves \(x_n\) sitting in the last slot, \(x=x_0=[a_0;\ldots,a_{n-1},x_n]\), which unfolds to

\[x_0=\frac{p_{n-1}x_n+p_{n-2}}{q_{n-1}x_n+q_{n-2}}.\]

Both sides lie in \(\mathbb Q(\sqrt d)\), and \(p_{n-1},p_{n-2},q_{n-1},q_{n-2}\) are integers, hence fixed by conjugation. Applying the conjugate to both sides and solving for \(\overline{x_n}\) gives

\[\overline{x_n}=-\frac{q_{n-2}}{q_{n-1}}\cdot\frac{\overline{x_0}-p_{n-2}/q_{n-2}}{\overline{x_0}-p_{n-1}/q_{n-1}}.\]

As \(n\to\infty\), both \(p_{n-2}/q_{n-2}\) and \(p_{n-1}/q_{n-1}\) converge to \(x_0\), while \(\overline{x_0}\neq x_0\) (they differ by \(2\sqrt d/s\neq0\)), so the fraction on the right tends to \(1\) and \(\overline{x_n}\to-q_{n-2}/q_{n-1}<0\). Hence \(\overline{x_n}<0\) for all sufficiently large \(n\).

On the other hand, \(x_n>1\) for every \(n\ge1\), being the reciprocal of a fractional part in \((0,1)\). So for large \(n\),

\[x_n-\overline{x_n}=\frac{2\sqrt d}{s_n}>0\quad\Longrightarrow\quad s_n>0.\]

Once \(s_n\) and \(s_{n+1}\) are both positive, \(s_ns_{n+1}=d-m_{n+1}^2\le d\) forces \(1\le s_n\le d\), so \(s_n\) takes only finitely many values for large \(n\); and then \(m_{n+1}^2=d-s_ns_{n+1}<d\) forces \(|m_{n+1}|<\sqrt d\), so \(m_n\) takes only finitely many values too. Consequently the pair \((m_n,s_n)\) takes only finitely many values for large \(n\), so by the pigeonhole principle there are indices \(i<j\) with \((m_i,s_i)=(m_j,s_j)\). Then \(x_i=x_j\), and since the reduction algorithm is entirely determined by \((m_k,s_k)\), the whole tail from index \(i\) onward repeats with period \(j-i\). This proves the converse of Lagrange's theorem: every quadratic irrational has an eventually periodic continued fraction.

Application: \(\sqrt N\)

Let \(N\) be a positive integer that is not a perfect square. Taking \(m_0=0\), \(s_0=1\), \(d=N\) in the reduction algorithm above — a valid standard form, since \(1\) divides everything — specializes it to the continued fraction of \(\sqrt N\) itself. Writing \(a_0=\lfloor\sqrt N\rfloor\), the recursion reads

\[m_{k+1}=a_ks_k-m_k,\qquad s_{k+1}=\frac{N-m_{k+1}^2}{s_k},\qquad a_k=\left\lfloor\frac{m_k+a_0}{s_k}\right\rfloor\text{ for }k\ge1,\]

the last identity because \(\lfloor x_k\rfloor\) can be computed from \(a_0=\lfloor\sqrt N\rfloor\) alone once \(m_k,s_k\) are known, with everything guaranteed to stay integral by the general result above. It can further be shown that the periodic block always begins right at \(a_1\) — the expansion of \(\sqrt N\) has the form \(\sqrt N=[a_0;\overline{a_1,\ldots,a_r}]\) with no non-repeating terms after \(a_0\) — and that the block \(a_1,\ldots,a_r\) reads the same forwards as backwards except for its last entry, which always equals \(2a_0\).

Example. For \(N=3\), \(a_0=\lfloor\sqrt3\rfloor=1\), \(m_0=0,s_0=1\):

\[ \begin{aligned} a_0&=1, & m_1&=1\cdot1-0=1, & s_1&=(3-1)/1=2,\\ a_1&=\lfloor(1+1)/2\rfloor=1, & m_2&=1\cdot2-1=1, & s_2&=(3-1)/2=1,\\ a_2&=\lfloor(1+1)/1\rfloor=2, & m_3&=2\cdot1-1=1, & s_3&=(3-1)/1=2, \end{aligned} \]

and the pair \((m_3,s_3)=(1,2)\) matches \((m_1,s_1)\), so the block \(a_1,a_2=1,2\) repeats forever:

\[\sqrt3=[1;\overline{1,2}].\]

As expected, the periodic block \(1,2\) is a single entry \(1\) followed by \(2a_0=2\).

Application: Pell's Equation

The convergents of \(\sqrt N\) are closely tied to Pell's equation \(x^2-Ny^2=1\), a Diophantine equation whose integer solutions are central to many problems in number theory. For \(N=3\), the first convergent past \(a_0\) is \(\frac{p_1}{q_1}=\frac{a_1a_0+1}{a_1}=\frac{2}{1}\), and indeed \(2^2-3\cdot1^2=4-3=1\): a solution to Pell's equation read directly off a convergent of \(\sqrt3\). In general, the convergent obtained by expanding \(\sqrt N\) through exactly one full period always produces such a solution, which is how continued fractions give a systematic method for solving Pell's equation for any non-square \(N\).

Continued Fraction Explorer

Convert a decimal number into its continued fraction and convergents:

Or compute the exact periodic continued fraction of \(\sqrt N\) for an integer \(N\):

Key Results

• Every real number \(x\) has a continued fraction \([a_0;a_1,a_2,\ldots]\), built by repeatedly taking the floor and inverting the remainder.
• The expansion is finite exactly for rational numbers, since applying the algorithm to \(p/q\) is the Euclidean algorithm for \(\gcd(p,q)\).
• Convergents \(p_n/q_n\) satisfy \(p_n=a_np_{n-1}+p_{n-2}\), \(q_n=a_nq_{n-1}+q_{n-2}\), are always in lowest terms, and satisfy \(p_nq_{n-1}-p_{n-1}q_n=(-1)^{n-1}\).
• Even convergents increase to \(x\), odd convergents decrease to \(x\), and \(|x-p_n/q_n|<1/(q_nq_{n+1})\), making convergents the best rational approximations to \(x\).
• The golden ratio \(\varphi=[1;1,1,1,\ldots]\) has convergents equal to ratios of consecutive Fibonacci numbers and is the hardest real number to approximate by fractions.
• By Lagrange's theorem, a continued fraction is eventually periodic exactly for quadratic irrationals; the exact terms are computed by an integer recursion on pairs \((m_n,s_n)\), and for \(\sqrt N\) specifically, the period starts right after \(a_0\).
• Convergents of \(\sqrt N\) give solutions to Pell's equation \(x^2-Ny^2=1\).