2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

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

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

$\endgroup$
  • $\begingroup$ What do you mean by collapsing given fraction part? $\endgroup$ – Vitaly B Oct 23 '15 at 13:58
  • $\begingroup$ @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$. $\endgroup$ – Abstraction Oct 23 '15 at 13:59
  • $\begingroup$ This answer is definitely not using the standard meaning for $p_k,q_k$ when talking about continued fractions. $\endgroup$ – Thomas Andrews Oct 23 '15 at 14:08
  • $\begingroup$ @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. $\endgroup$ – Abstraction Oct 23 '15 at 14:14
  • 1
    $\begingroup$ 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. $\endgroup$ – Thomas Andrews Oct 23 '15 at 14:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.