RSS
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.
Problem ID: 286 (01 Aug 2006) Difficulty: 4 Star
Show Solution
Hide Solution