Prove that any rational number is positive $\frac{m}{n}$ Can be displayed in the form of a "continued fraction"

Question

"Continued fraction" is an expression of the form

$[a_{0},a_{1},a_{2}...,a_{n}]= > a_{0}+\frac{1}{a_{1}+\frac{1}{a_{2}+\frac{1}{a_{3}+_{\frac{1}{...+}}}}}$

$a_{0},a_{1},a_{2}...,a_{n}$ are natural numbers. Example: $\frac{275}{52}=[5,3,2,7]= 5+\frac{1}{3+\frac{1}{2+\frac{1}{7}}}$

Prove that any rational number is positive $\frac{m}{n}$ Can be displayed in the form of a "continued fraction" (induction for n)

I think for proving with induction start with base (n=1), we get [1]= 1+1=2

then assuming $[a_{0},a_{1},a_{2}...,a_{n}]$ is a rational number, then we need to prove that $[a_{0},a_{1},a_{2}...,a_{n},a_{n+1}]$ is rational

But I don't know how to continue from here

Answer 1

Here is a proof by induction that any positive rational number $\frac{m}{n}$ can be written as a finite continued fraction (i.e., a continued fraction $[a_0,a_1,\ldots,a_N]$ with a finite number of entries). The induction is on the numerator $n$.

If $n=1$, the proposition is true: $\frac{m}{1}=m=[m]$.

Let's now assume that for all $k$ such that $1\leq k\leq n$ it is possible to represent a positive rational number $\frac{m}{k}$ as a finite continued fraction. Then the same is true if $1\leq k\leq n+1$. Indeed, $\frac{m}{n+1}=a+\frac{r}{n+1}$, where $0\leq r\le n$. If $r=0$, we are done ($\frac{m}{n+1}=a=[a]$). If $r>0$, then $\frac{r}{n+1}=1/\frac{n+1}{r}$; since $r\leq n$, the denominator of the latter fraction can be represented as a finite continued fraction, i.e., $\frac{n+1}{r}=[b_0,b_1,\ldots,b_q]$, so that $\frac{m}{n+1}=a+1/[b_0,b_1,\ldots,b_q]=[a,b_0,b_1,\ldots,b_q]$. $\square$

Answer 2

It's an algorithm, extended Euclidean Algorithm done, deliberately, in the terminology of continued fractions.

$$ \frac{ 275 }{ 52 } = 5 + \frac{ 15 }{ 52 } $$ $$ \frac{ 52 }{ 15 } = 3 + \frac{ 7 }{ 15 } $$ $$ \frac{ 15 }{ 7 } = 2 + \frac{ 1 }{ 7 } $$ $$ \frac{ 7 }{ 1 } = 7 + \frac{ 0 }{ 1 } $$ Simple continued fraction tableau:
$$ \begin{array}{cccccccccc} & & 5 & & 3 & & 2 & & 7 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 5 }{ 1 } & & \frac{ 16 }{ 3 } & & \frac{ 37 }{ 7 } & & \frac{ 275 }{ 52 } \end{array} $$

and we can read off $$ $$ $$ 275 \cdot 7 - 52 \cdot 37 = 1 $$

$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$

$$ \frac{ 479 }{ 231 } = 2 + \frac{ 17 }{ 231 } $$ $$ \frac{ 231 }{ 17 } = 13 + \frac{ 10 }{ 17 } $$ $$ \frac{ 17 }{ 10 } = 1 + \frac{ 7 }{ 10 } $$ $$ \frac{ 10 }{ 7 } = 1 + \frac{ 3 }{ 7 } $$ $$ \frac{ 7 }{ 3 } = 2 + \frac{ 1 }{ 3 } $$ $$ \frac{ 3 }{ 1 } = 3 + \frac{ 0 }{ 1 } $$ Simple continued fraction tableau:
$$ \begin{array}{cccccccccccccc} & & 2 & & 13 & & 1 & & 1 & & 2 & & 3 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 2 }{ 1 } & & \frac{ 27 }{ 13 } & & \frac{ 29 }{ 14 } & & \frac{ 56 }{ 27 } & & \frac{ 141 }{ 68 } & & \frac{ 479 }{ 231 } \end{array} $$ $$ $$

so that we get Bezout (little 2 by 2 determinant): $$ 479 \cdot 68 - 231 \cdot 141 = 1 $$ $$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$