 ## Continued Fraction Irreducible Convergents

#### Problem

Any real number, $\alpha$, can be represented as a continued fraction which may either terminate or be infinite (repeating or non-repeating).

$\alpha = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + ...}}}$

Let $\dfrac{p_n}{q_n}$ be defined as the $n$th convergent:

$\dfrac{p_n}{q_n} = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + ... + \cfrac{1}{a_n}}}}$

For example, $\sqrt{2} = 1 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{2 + ...}}}$

And the first five convergents are:

\begin{align}\dfrac{p_0}{q_0} &= 1\\\dfrac{p_1}{q_1} &= \dfrac{3}{2}\\\dfrac{p_2}{q_2} &= \dfrac{7}{5}\\\dfrac{p_3}{q_3} &= \dfrac{17}{12}\\\dfrac{p_4}{q_4} &= \dfrac{41}{29}\\\end{align}

Assuming that the following recurrence relation holds for $n \ge 2$ for all continued fractions:

\begin{align}p_n &= a_n p_{n-1} + p_{n-2}\\q_n &= a_n q_{n-1} + q_{n-2}\end{align}

Prove that $\dfrac{p_n}{q_n}$ is irreducible.

#### Solution

Let us consider the difference between two consecutive convergents:

$${p_{k+1} \over q_{k+1}} - {p_k \over q_k} = {p_{k+1} q_k - p_k q_{k+1} \over q_k q_{k+1}} = {D_k \over q_k q_{k+1}}$$

Multiplying through by $q_k q_{k+1}$:

\begin{align}D_k &= p_{k+1} q_k - p_k q_{k+1}\\&= (a_{k+1} p_k + p_{k-1}) q_k - p_k (a_{k+1} q_k +q_{k-1})\\&= a_{k+1} p_k q_k + p_{k-1} q_k - a_{k+1} p_k q_k - p_k q_{k-1}\\&= p_{k-1} q_k - p_k q_{k-1}\\&= -(p_k q_{k-1} - p_{k-1} q_k)\\&= -D_{k-1}\end{align}

$\therefore D_k = -D_{k-1} = D_{k-2} = ... = (-1)^k D_0$.

But $D_0 = p_1 q_0 - p_0 q_1$, and from the definition of the continued fraction, $\dfrac{p_0}{q_0} = a_0 \implies p_0 = a_0$ and $q_0 = 1$ (as $p_k$ and $q_k$ are integer).

Similarly $\dfrac{p_1}{q_1} = a_0 + \dfrac{1}{a_1} = \dfrac{a_0 a_1 + 1}{a_1} \implies p_1 = a_0 a_1 + 1$ and $q_1 = a_1$.

$\therefore D_0 = (a_1 a_0 + 1) \times 1 - a_0 a_1 = 1. Hence$D_k = (-1)^k$. Let$j$be the highest common factor of$p_n$and$q_n$; that is,$p_n = j p_n'$and$q_n = j q_n'. \begin{align}\therefore D_k &= p_{k+1} q_k - p_k q_{k+1}\\&= p_{k+1} j q_{k+1}' - j p_k' q_{k+1}\\&= j(p_{k+1} q_k' - p_k' q_{k+1})\end{align} But asD_k = (-1)^k$we get,$(-1)^k = j(p_{k+1} q_k' - p_k' q_{k+1})$. Clearly the left hand side is only divisible by 1, and so we conclude that the highest common factor,$j = 1$. Hence$\dfrac{p_n}{q_n}$is irreducible. By considerig$\dfrac{p_{k+1}}{q_{k+1}} - \dfrac{p_k}{q_k}$prove that$\dfrac{p_n}{q_n}$converges as$n\$ increases.

Problem ID: 286 (01 Aug 2006)     Difficulty: 4 Star

Only Show Problem