Show that the elimination of the successive remainders from the Euclidean algorithm leads to a finite expansion.

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

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

• @Compact answer given – user2661923 Jun 1 '18 at 18:45