Skip to main content

Section 11.2 Convergents

Definition 11.2.1.

The continued fraction made by cutting off \([a_0; a_1,..., a_n]\) after the \(k\)th partial quotient \(a_k\) is called the \(k\)th convergent of the continued fraction and denoted by \(C_k.\) By convention, we denote the zeroth convergent by \(C_0 = a_0.\)

Note that we have \(19/51 = [0; 2, 1, 2, 6].\) The convergents are

\begin{align*} C_0 \amp = 0\\ C_1 \amp= [0; 2] = 0 + \frac{1}{2}=\frac{1}{2} \\ C_2 \amp= [0; 2, 1] = 0 + \frac{1}{2+\frac{1}{1}}=\frac{1}{3}\\ C_3 \amp= [0; 2, 1, 2] = 0 + \frac{1}{2+\frac{1}{1+\frac{1}{2}}}=\frac{3}{8}\\ C_4 \amp= [0; 2, 1, 2, 6] = 19/51 \end{align*}

Note that until we get to \(C_4\) the convergents are alternatively greater than and less than \(19/51.\)

We can make things a little easier by creating a recurrence for the numerators and denominators of the convergents. We have the following theorem.

Definition 11.2.3.

Define the numbers \(p_k\) and \(q_k \hspace{2mm} (k = 0, 1,..., n)\) by \(p_0 = a_0, q_0 = 1, p_1 = a_1a_0 + 1, q_1 = a_1,\) and for \(k = 2, 3,..., n\) we have

\begin{equation*} p_k = a_kp_{k-1} + p_{k-2} \hspace{5mm} \text{ and } \hspace{5mm} q_k = a_kq_{k-1} + q_{k-2}. \end{equation*}

The above example motivates us to start with computing the first few convergents based on the definitions. We have

\begin{align*} C_0 \amp= a_0\\ C_1 \amp= a_0 +\frac{1}{a_1}=\frac{a_1a_0+1}{a_1}=\frac{p_1}{q_1}\\ C_2 \amp= a_0 +\frac{1}{a_1+\frac{1}{a_2}}=\frac{a_2(a_1a_0+1)+a_0}{a_2a_1+1}=\frac{p_2}{q_2}. \end{align*}

Now suppose that the theorem is true for \(k = m\) where \(2\leq m \lt n.\) So we have

\begin{equation*} C_m = [a_0; a_1,..., a_m] = \frac{p_m}{q_m}=\frac{a_mp_{m-1}+p_{m-2}}{a_mq_{m-1}+q_{m-2}}. \end{equation*}

Note that the integers \(p_{m-1}, q_{m-1}, p_{m-2},\) and \(q_{m-2}\) depend on the first \(m-1\) partial denominators \(a_1, a_2,..., a_{m-1}\) and hence, are independent of \(a_m.\) Thus in the above equation for \(C_m\) we can replace \(a_m\) by \(a_m + \frac{1}{a_{m+1}}\) to get

\begin{align*} C_{m+1} \amp = [a_0; a_1,..., a_m, a_{m+1}]\\ \amp =\left[a_0; a_1,..., a_{m-1}, a_m +\frac{1}{a_{m+1}}\right]\\ \amp =\frac{\left(a_m +\frac{1}{a_{m+1}}\right)p_{m-1}+p_{m-2}}{\left(a_m +\frac{1}{a_{m+1}}\right)q_{m-1}+q_{m-2}}\\ \amp =\frac{a_{m+1}(a_mp_{m-1}+p_{m-2})+p_{m-1}}{a_{m+1}(a_mq_{m-1}+q_{m-2})+q_{m-1}}\\ \amp =\frac{a_{m+1}p_{m}+p_{m-1}}{a_{m+1}q_{m}+q_{m-1}}\\ \amp =\frac{p_{m+1}}{q_{m+1}}. \end{align*}

This proves the theorem.

Again we use induction. When \(k = 1,\) we have

\begin{equation*} p_1q_0-q_1p_0 = (a_1a_0 + 1)\cdot 1-a_1a_0 = 1 = (-1)^{1-1}. \end{equation*}

Now suppose that the theorem holds for \(k = m\) where \(1\leq m\lt n.\) Then

\begin{align*} p_{m+1}q_m -q_{m+1}p_m \amp= (a_{m+1}p_m + p_{m-1})q_m -(a_{m+1}q_m + q_{m-1})p_m\\ \amp = -(p_mq_{m-1}-q_mp_{m-1})\\ \amp = -(-1)^{m-1}\\ \amp = (-1)^m. \end{align*}

Thus by induction the theorem is valid for all \(k\) with \(1\leq k \leq n.\)

We have the following corollary.

We use the previous theorem. If \(d = \gcd(p_k, q_k)\) then \(d\vert (-1)^{k-1}.\) Since \(d \gt 0\) we have that \(d = 1.\)