Are the numerator and the denominator of a convergent of a continued fraction always coprime?

Question

Is it true that for a convergent $A_k = p_k/q_k$ of the continued fraction expansion $[a_0;a_1,a_2,\dots]$ the numerator $p_k$ and the denominator $q_k$ are always coprime? If yes, how would one show it? My thought is that it is somehow follows from the way we construct the continued fraction, but I couldn't give an argument.

Answer 1

In general, you can prove by induction that if $\frac{P_k}{Q_k},\frac{P_{k+1}}{Q_{k+1}}$ are sequential continued fraction convergents, then:

$$P_kQ_{k+1}-Q_kP_{k+1} = \pm 1$$

This in particular means that $P_k,Q_k$ are relatively prime.

The induction is fairly easy, using $P_{k+2}=a_{k+2}P_{k+1}+P_k$ and $Q_{k+2}=a_{k+2}Q_{k+1}+Q_k$.

Answer 2

When you collapse given fraction part (computing resulting numerator and denominator), you get iteratively ${b_k \over c_k} = {1 \over {a_k + {b_{k+1} \over c_{k+1}}}} = {c_{k+1} \over {a_kc_{k+1} + b_{k+1}}}$, where $c_n = a_n, b_n=1$ and ${a_0c_1+b_1 \over c_1}$ is resulting fraction ($P_n \over Q_n$). It's easy to see that $gcd(b_n,c_n)=1$, $(gcd(b_{i+1},c_{i+1})=1 \implies gcd(b_i,c_i)=1)$ and thus $gcd(a_0c_1+b_1,c_1)=1$.