Proof that continued fractions are finite for rationals? How does one prove that the continued fraction representations of rational numbers are finite? 
For every $x\in\mathbb{R}$, the (simple) continued fraction representation of $x$ is:
$$
  x = [a_0; a_1, a_2, ...] = a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{...}}}
$$
where $a_0\in\mathbb{Z}$ and $a_k\in\mathbb{N}$ for $k\geq 1$, which are themselves obtained as follows:
$$
\begin{align}
  r_0 &= x \\
  \forall k \geq 0,\quad a_k &= \lfloor r_k \rfloor \\
  \forall k \geq 0,\quad r_{k+1} &= 
\begin{cases}
1 / (r_k-a_k) & \text{if } r_k > a_k \\ 
0 & \text{otherwise}
\end{cases}
\end{align}
$$
and if there exists $n$ for which $r_n > r_{n+1} = 0$, then we correct $a_n\mapsto 
 a_n-1$.
Clearly if the sequence $a_k$ converges to 0, then $x$ is rational. But the converse does not seem trivial at all; why does this recursion necessarily terminate if $x = p/q$? Contraposition does not seem evident to me here either. Is there another way to think about this?

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