There are many situations where we want to approximate a real number by a rational number. For example, we can approximate $\pi =3.14159265\dots$ by $314/100=157/50\text{.}$ But $22/7$ is a slightly better approximation, and it is more efficient in the sense that it uses a smaller denominator than $157/50\text{.}$ The method of continued fractions is a procedure that yields this type of good approximations. In this section, we summarize some basic facts. For proofs and more details, see, for example, [Hardy-Wright], [Niven et al.], [Rosen], and [KraftW].

An easy way to approximate a real number $x$ is to take the largest integer less than or equal to $x\text{.}$ This is often denoted by $[x]\text{.}$ For example, $[\pi ]=3\text{.}$ If we want to get a better approximation, we need to look at the remaining fractional part. For $\pi =3.14159\dots \text{,}$ this is $.14159\dots \text{.}$ This looks close to $1/7=.142857\dots \text{.}$ One way to express this is to look at $1/.14159=7.06251\text{.}$ We can approximate this last number by $[7.06251\dots ]=7$ and therefore conclude that 1/7 is indeed a good approximation for $.14159$ and that $22/7$ is a good approximation for $\pi \text{.}$ Continuing in this manner yields even better approximations. For example, the next step is to compute $1/.06251=15.9966$ and then take the greatest integer to get 15 (yes, 16 is closer, but the algorithm corrects for this in the next step). We now have

If we continue one more step, we obtain

This last approximation is very accurate:

This procedure works for arbitrary real numbers. Start with a real number $x\text{.}$ Let $a_0=[x]$ and $x_0=x\text{.}$ Then (if $x_i\ne a_i\text{;}$ otherwise, stop) define

We obtain the approximations

We have therefore produced a sequence of rational numbers $p_1/q_1\text{,}{p}_2/q_2\text{,}\dots \text{.}$ It can be shown that each rational number $p_k/q_k$ gives a better approximation to $x$ than any of the preceding rational numbers $p_j/q_j$ with $1\le j<k\text{.}$ Moreover, the following holds.

For example, $|\pi -22/7|\approx .001<1/98$ and $22/7=p_2/q_2\text{.}$

Continued fractions yield a convenient way to recognize rational numbers from their decimal expansions. For example, suppose we encounter the decimal 3.764705882 and we suspect that it is the beginning of the decimal expansion of a rational number with small denominator. The first few terms of the continued fraction are

The fact that 9803921 is large indicates that the preceding approximation is quite good, so we calculate

which agrees with all of the terms of the original 3.764605882. Therefore, $64/17$ is a likely candidate for the answer. Note that if we had included the 9803921, we would have obtained a fraction that also agrees with the original decimal expansion but has a significantly larger denominator.

Now let’s apply the procedure to $12345/11111\text{.}$ We have

This yields the numbers

Note that the numbers 1, 9, 246, 1, 4 are the quotients obtained during the computation of $gcd(12345\text{,}11111)$ in Subsection 3.1.3 (see Exercise 49).

Calculating the fractions such as

can become tiresome when done in the straightforward way. Fortunately, there is a faster method. Define

Then

Using these relations, we can compute the partial quotients $p_n/q_n$ from the previous ones, rather than having to start a new computation every time a new $a_n$ is found.