The Euclidean algorithm

Given integers $a$ and $b$ with $b > 0$, there exists a unique pair of integers $q$ and $r$ such that $ a = bq+r$, with $0 \le r < b$. Moreover, $r=0$ if, and only if, $b|a$.

Proof. TODO

The Euclidean algorithm. Given positive integers a and b, where $b\not | a$. Let $r_0=a, r_1=b$, and apply the division algorithm repeatedly to obtain a set of remainders $r_2,r_3,...,r_n,r_{n+1}$ defined successively b the relations

                       $ r_0 = r_1q_1 + r_2,  \;\; 0<r_2<r_1,$
                       $ r_1 = r_2q_2 + r_3,  \;\; 0<r_3<r_2,$
                                              .
                                              .
                                              .
                       $ r_{n-2} = r_{n-1}q_{n-1} + r_n,  \;\; 0<r_n<r_{n-1},$
                       $ r_{n-1} = r_{n}q_{n} + r_{n+1},  \;\; r_{n+1}=0,$

Then $r_n$, the last nonzero remainder is the gcd of $a$ and $b$. 

Proof. TODO