> [!NOTE] Theorem (Euclidean algorithm terminates and is valid) >The above algorithm on $a,b$ > 1. terminates: $\exists k\in\mathbb{N}$ such that $r_{k-1}=q_{k+1}r_{k}+r_{k+1}$ and $r_{k}=q_{k+2}r_{k+1}+0$ > 2. and in this case $r_{k+1}=\gcd(a,b)$ is the [[Greatest Common Divisor (GCD)|gcd]] of $a$ and $b.$ *Proof.* (1) Note that we have $b>r_{1}> r_{2} >r_{3} > \dots \geq 0$. So $(r_{i})$ is strictly decreasing and bounded below by $0$ so $r_{i}\to 0$ as $i$ increases. Thus, there must be a $k\in\mathbb{N}$ such that $r_{k+2}=0.$ (2) Consider one step in the algorithm:$r_{i}=q_{i+2}r_{i+1}+r_{i+2}$we show common divisor's of $r_{i}$ and $r_{i+1}$ are the same as for $r_{i+1}$ and $r_{i+2}$. This is since if $m\mid r_{i}$ and $m\mid r_{i+1}$ then $r_{i+2}=r_{i}-q_{i+2}r_{i+1}$ so $m\mid r_{i+2}$ and also if $n\mid r_{i+1}$ and $n \mid r_{i+2}$ then $r_{i}=q_{i+2}r_{i+1} +r_{i+2}$ so $n\mid r_{i}.$ So every step of Euclid's algorithm preserves the set of common divisors, so preserve the greatest common divisor. The final pair of remainders is $\{ r_{k},r_{k+1} \}$ but $r_{k}=q_{k+2}r_{k+1}+0$ so $\gcd(r_{k},r_{k+1})=r_{k+1}$ and so $\gcd(a,b)=r_{k+1}.$