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?
 A: 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 $$ 
A: The only way for this recursion to terminate, is for the sequence of $a_k$ to converge to $0$, and this only happens when one of the $r_k$ becomes an integer. 
If this is unclear to you, consider that $\forall x\in\mathbb{R},\ x-\lfloor x\rfloor\in[0,1)$; therefore the only way that the $a_k$ converges to zero is if at some point $r_k = \lfloor r_k\rfloor$, i.e. $r_k$ is an integer. It is easy to see that once this happens, all further $r_k$ and $a_k$ are zero. (Note also that $a_0$ can be zero without implying convergence, which is not the case for any subsequent $a_k$.)
The main thing that changes if $x$ is a rational, is that the $r_k$ are all rational as well (subtraction with integer and reciprocal of a non-zero are both inverse of elementary operations in $\mathbb{Q}$).

For all $k>0$, $r_k$ is either integral or a rational greater than 1.

Proof:
If any $r_{k\geq 0}$ is integral, then all successors are zero.
If $r_0$ is a rational less than 1, then $0 < r_0 - \lfloor r_0 \rfloor < 1$ and therefore $r_1 > 1$. Similarly if $r_k = p/q$ with $p > q > 0$ for some $k > 0$, then:
$$
  \exists n\in\mathbb{N},\quad 0 < n < \frac{p}{q} < n+1
  \quad\implies\quad
  a_k = n \quad\text{and}\quad r_{k+1} = \frac{q}{p-nq}
$$
with $p - nq < q$ (because $n$ is such that $p < (n+1)q$).

Incidentally, this also shows that the sequence of denominators of $r_k$ for $k > 0$ is strictly decreasing, as long as the sequence consists of rationals. Since these denominators are bounded below by zero, and that the previous induction applies for values greater than one, we will necessarily find a term $r_K = p/q$ for which either $q|p$ (integer case) or $p \equiv 1 \mod q$ (in which case $r_{K+1}$ is an integer).
