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

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.

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$.

• Thanks, that's much more clear! – Vitaly B Oct 23 '15 at 14:20

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$.

• What do you mean by collapsing given fraction part? – Vitaly B Oct 23 '15 at 13:58
• @VitalyB I mean a process when you go from $a_0+{1 \over a_1 + {1 \over a_2 + ...}}$ to $P_k \over Q_k$. – Abstraction Oct 23 '15 at 13:59
• This answer is definitely not using the standard meaning for $p_k,q_k$ when talking about continued fractions. – Thomas Andrews Oct 23 '15 at 14:08
• @ThomasAndrews True, but I needed some notation for fractions appearing when computing numerator and denominator. If you think that using something like $(b_n, c_n)$ will be better, I can edit my answer. – Abstraction Oct 23 '15 at 14:14
• But the question uses $p_k,q_k$ for the standard meaning, and here you've used something non-standard which is absolutely going to be confusing. – Thomas Andrews Oct 23 '15 at 14:15