Given a real number or a rational with large integers , how can we approximate this by a rational with small integers?

Let’s recall the Euclidean algorithm to find via the following example:

In general, for , we use , which is much faster than factorization!

To see this algorithm in another setting, we recall continued fractions. For this, we will consider the example of approximating by a rational.

*Theorem 1.*

For any integer , the best rational approximation of any real using denominator at most is given by a continued fraction approximation of .

The theorem will follow from the next lemma.

*Lemma 2.*

unique such that

from is given by some

*Proof.*

is left as homework.

is by substitution. Note that alternates in sign and converges.

with

But for any two ,

, where we reach a contradiction.

Suppose such that

For $latex q_k \leq B |\frac{a}{b}-r| \geq \min(|\frac{a}{b} – \frac{p_k}{q_k}|, |\frac{a}{b}-\frac{p_{k+1}}{q_{k+1}}|)$

So,

But such a solution is unique!

We will now use lemma 2 to complete our algorithm for solving exactly. Recall we have where . For each , our goal is to find such that

Then, since .

*Lemma 3.*

Suppose integers such that and .

Let the continued fraction approximations of be and define .

Let be the smallest integer such that . Then, .

This lemma solves our problem. We can quickly convert to a rational solution via the continued fraction approximations of and finding the corresponding .

*Proof.*

Note that are increasing while is decreasing (why?). Let . Then,

By Lemma 2, must be some .

, so , since is decreasing.

But and

i.e. and .