2
$\begingroup$

Show that the elimination of the successive $r_i$ from the Euclidean algorithm, $$a = bq_1 + r_1,\text{ } b = r_1q_2 + r_2, \text{ etc.}$$ leads to the finite expansion $a/b = \{ q_1; q_2, \cdots \}$.

For clarification, the expression above is using continued fraction notation; for example, $$[2;1,3,4] = 2 + \frac{1}{1+\frac{1}{3+\frac{1}{4}}} = \frac{47}{17}.$$ I have a rough idea of this, but do not know how to formally write a proof of the result using continued fractions. [We know that Euclidean algorithm terminates since at each step one of the two integers decreases, and at the next step so does the other.]

$\endgroup$
1
$\begingroup$

$\underline{\text{case}\;1}$
$a=q_1\times b + r_1$
$b=q_2\times r_1$

Then $r_1 = \frac{b}{q_2} \Rightarrow \frac{a}{b} = q_1 + \frac{r_1}{b} = q_1 + \frac{1}{q_2} = [q_1;q_2].$

$\underline{\text{case}\;2}$
$a=q_1\times b + r_1$
$b=q_2\times r_1 + r_2$
$r_1=q_3\times r_2 + r_3$
$\cdots$
$r_{n-3}=q_{n-1}\times r_{n-2} + r_{n-1}$
$r_{n-2}=q_n\times r_{n-1}$

By inductive assumption, $\frac{b}{r_1} = [q_2; q_3, \cdots, q_n] \Rightarrow$
$\frac{a}{b} = q_1 + \frac{r_1}{b} = q_1 + \frac{1}{[q_2; q_3, \cdots, q_n]} = [q_1; q_2, \cdots, q_n].$

$\endgroup$
  • $\begingroup$ @Compact answer given $\endgroup$ – user2661923 Jun 1 '18 at 18:45

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.