Proof that continued fractions are finite for rationals?
Solution 1:
it is the Euclidean Algorithm, that is all. Lots of people use "back-substitution" to finish the Extended Algorithm and find the Bezout combination, I prefer to write this as a continued fraction.
$$ \gcd( 12345, 1601 ) = ??? $$
$$ \frac{ 12345 }{ 1601 } = 7 + \frac{ 1138 }{ 1601 } $$
$$ \frac{ 1601 }{ 1138 } = 1 + \frac{ 463 }{ 1138 } $$
$$ \frac{ 1138 }{ 463 } = 2 + \frac{ 212 }{ 463 } $$
$$ \frac{ 463 }{ 212 } = 2 + \frac{ 39 }{ 212 } $$
$$ \frac{ 212 }{ 39 } = 5 + \frac{ 17 }{ 39 } $$
$$ \frac{ 39 }{ 17 } = 2 + \frac{ 5 }{ 17 } $$
$$ \frac{ 17 }{ 5 } = 3 + \frac{ 2 }{ 5 } $$
$$ \frac{ 5 }{ 2 } = 2 + \frac{ 1 }{ 2 } $$
$$ \frac{ 2 }{ 1 } = 2 + \frac{ 0 }{ 1 } $$
Simple continued fraction tableau:
$$
\begin{array}{cccccccccccccccccccc}
& & 7 & & 1 & & 2 & & 2 & & 5 & & 2 & & 3 & & 2 & & 2 & \\
\frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 7 }{ 1 } & & \frac{ 8 }{ 1 } & & \frac{ 23 }{ 3 } & & \frac{ 54 }{ 7 } & & \frac{ 293 }{ 38 } & & \frac{ 640 }{ 83 } & & \frac{ 2213 }{ 287 } & & \frac{ 5066 }{ 657 } & & \frac{ 12345 }{ 1601 }
\end{array}
$$
$$ $$
$$ 12345 \cdot 657 - 1601 \cdot 5066 = -1 $$