Convergents are Best Approximations

Theorem

Let $\dfrac {p_n} {q_n}$ be the $n$th convergent of the irrational number $x$.

Let $\dfrac a b$ be any rational number such that $0 < b < q_{n+1}$.

Then:

$\forall n > 1: \left\vert{q_n x - p_n}\right\vert \le \left\vert{b x - a}\right\vert$.

The equality holds only if $a = p_n$ and $b = q_n$.

Corollary

Let $\dfrac {p_1} {q_1}, \dfrac {p_2} {q_2}, \ldots$ be the convergents of the irrational number $x$.

Then for any rational number $\dfrac a b$ such that $1 \le b \le q_n$:

$\left\vert{x - \dfrac {p_n} {q_n}}\right\vert \le \left\vert{x - \dfrac a b}\right\vert$.

The equality holds only if $a = p_n$ and $b = q_n$.

Proof

Let $\dfrac a b$ be a rational number in canonical form such that $b < q_{n+1}$.

Suppose it is not true that $a = p_n$ and $b = q_n$, in which case the equality certainly holds.

Consider the system of equations:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle a\)	\(=\)	\(\displaystyle r p_n + s p_{n-1}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle b\)	\(=\)	\(\displaystyle r q_n + s q_{n-1}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

Multiplying the first by $b_n$, and the second by $a_n$, then subtracting, we get:

$a q_n - b p_n = s \left({p_{n+1} q_n - p_n q_{n+1}}\right)$.

After applying Properties of Convergents of Continued Fractions we get:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle s\)	\(=\)	\(\displaystyle \left({-1}\right)^{n+1} \left({a q_n - b p_n}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle r\)	\(=\)	\(\displaystyle \left({-1}\right)^{n+1} \left({b p_{n+1} - a q_{n+1} }\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	by a similar process

So $r$ and $s$ are integers.

Neither of them is $0$ because:

• if $r = 0$ then $a q_{n+1} = b p_{n+1}$, and Euclid's Lemma means $q_{n+1} \backslash b$ as $p_{n+1} \perp q_{n+1}$, which contradicts $0 < b < q_{n+1}$
• if $s = 0$ we have $\frac a b = \dfrac {p_n} {q_n}$ and this we have already excluded as a special case.

Now since $0 < b = r q_n + s q_{n+1} < q_{n+1}$ the integers $r$ and $s$ must have opposite sign.

(This is because the convergents are alternately greater than and less than $x$ from Relative Sizes of Convergents of Simple Continued Fraction.

It follows that $r \left({q_n x - p_n}\right)$ and $s \left({q_{n+1} x - p_{n+1}}\right)$ have the same sign.

(This is necessary so we can use the Triangle Inequality.)

So:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \left\vert{b x - a}\right\vert\)	\(=\)	\(\displaystyle \left\vert{\left({r q_n + s q_{n+1} }\right) x - \left({r p_n + s p_{n+1} }\right)}\right\vert\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left\vert{r \left({q_n x - p_n}\right) + s \left({q_{n+1} x - p_{n+1} }\right)}\right\vert\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left\vert{r}\right\vert \left\vert{q_n x - p_n}\right\vert + \left\vert{s}\right\vert \left\vert{q_{n+1} x - p_{n+1} }\right\vert\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(>\)	\(\displaystyle \left\vert{r}\right\vert \left\vert{q_n x - p_n}\right\vert\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\ge\)	\(\displaystyle \left\vert{q_n x - p_n}\right\vert\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

as we wanted to prove.

$\blacksquare$

Proof of Corollary

Assume otherwise, i.e. that $\exists \dfrac a b$ such that $1 \le b \le q_n$ and $\left\vert{x - \dfrac {p_n} {q_n}}\right\vert > \left\vert{x - \dfrac a b}\right\vert$.

Then:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \left\vert{q_n x - p_n}\right\vert\)	\(=\)	\(\displaystyle q_n \left\vert{x - \frac {p_n} {q_n} }\right\vert\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(>\)	\(\displaystyle q_n \left\vert{x - \frac a b}\right\vert\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\ge\)	\(\displaystyle b \left\vert{x - \frac a b}\right\vert\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left\vert{b x - a}\right\vert\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

which contradicts the result of the theorem.

$\blacksquare$