Something kind of like proving the euclidean Algorithm by induction Let a > b be positive integers. In applying the Euclidean algorithm,
we have $a = b q_0$ + $r_0$, $b = r_0 q_1 + r_1$, and $r_{n-1} = r_n q_{n+1} + r_{n+1}$, for all $n > 0$. Prove by induction that $r_n$ is in the set $\{ka + lb\}$  such that l and k are integers every $n>-1$
This i find very frustrating but i am horrible at induction :), 
i started with my base case's $s=0,1$ 
$r_0 = a - b q_0$ 
$b = r_0 q_1 r_1$ thus $r_1 = b - r_0 q_1$ 
from there i assume ( cause i have no idea what else to do) $r_1$ must divide b and $r_0$ which it should but may not be useful to me.
Now i assume that its true for $r_d$ and $r_{d-1}$ and want to show it for $r_s+1$
well  $r_{d+1} = r_{d-1} - r_d q_{d+1}$  and now im lost, though im fairly certain i was lost at prove by induction :)
im certain if i can prove divisibility here with this step i can merely write a and b as multiples of $r_n$ and show that it divides the set.
That being said i could very well be on the wrong track altogether any advice much appreciated. 
 A: Here are steps to show the question you pose in the last sentence of your first paragraph, which I think is your question:
(1) Let $\mathbb{Z} m := \{ x m | x \in \mathbb{Z} \}$. Show: every subgroup of the additive group of the integers is of form $\mathbb{Z} m$, with $m$ being the smallest positive integer in the subgroup. (proof outline: (a) Let $H$ be any subgroup. If it is trivial ($H = \{0 \}$), $H = \mathbb{Z} 0$; if not, it contains an integer $x$, and so, as it is a subgroup, also $-x$, so it contains a positive integer. Call the smallest such integer $m$; (b) show, using $H$ is a subgroup, that $\mathbb{Z} m \subset H$: $mk = m + \dots m \in H, -mk \in H, 0 = 0m$ as well (immediate as $H$ is a subgroup); (c) using Euclid, write any $n \in H$ as $n = qm + r, q, r \in \mathbb{Z}, 1 \leq r < m$. $qm \in H$ by (b), and $n$ by choice, so also $r = n - qm$ as $H$ is a subgroup. But by our definition of $m$ as the smallest positive integer in $H$, and $0 \leq r < m$, then $r= 0$, and so $n = qm$, which was to be shown.). 
(b) by (a), $\{ka + lb, k, l \in \mathbb{Z} \} = \mathbb{Z} m$ for $m$ the smallest positive integer in this subgroup. Now it is easy to show: (1) there are integers $r, s$ such that $m = ra + sb$ (Bezout's identity: as $m = 1 m \in \mathbb{Z} m$); (2) $m$ divides $a$ and $b$ (directly from (1)); and (3) if an integer $d$ divides $a$ and $b$, it also divides $m$ (also directly from (1)). But (2) and (3) are the definition of the greatest common divisor, so you are done, as euclid's algorithm has $r_n = \operatorname{gcd}(a, b)$.
A: All the $q_n$ are integers.
Base case n=0: $$r_0 = 1 * a - q_0 b,$$  so $r_0$ is in the set with $k = 1$ and $l = q_0$. 
For n=1: $$r_1 = b - q_1 r+0 \\ = b - q_1 (a - q_0 b) \\ = -q_1 a + (1-q_0)b,$$ so $r_1$ is in the set with $k = -q_1$ and $l = 1 - q_0$.
Rearrange your formula for $r_{n+1}.$  Assuming that $r_{n-1}, r_n$ are integer multiples of a plus integer multiples of b, then you can show that $r_{n+1}$ is too.  
A: Hint $\, $ The set $\rm\,I = a\,\Bbb Z + b\,\Bbb Z\subset \Bbb Z\,$ is closed under $\rm\color{#C00}{addition}$ and $\rm\color{#0A0}{scalings}$ by $\rm\,\color{#0A0}n\in \Bbb Z.\:$ Indeed, $\rm\,ai\!+\!bj \color{#C00}{\bf +} (ai'\!+\!bj') = a(i\!+\!i')+b(j\!+\!j')\in S,\ $ and $\rm\,\ \color{#0A0}{\bf n}\,(ai+bj) = a(ni) + b(nj)\in S.$
Therefore, by scaling closure $\rm\,r_n \in I\,\Rightarrow\, \color{#0A0}{q_{n+1}} r_n\in I.\,$ Adding $\rm\,r_{n-1}\in I\,$ to this yields $\rm\,r_{n+1}\in I,$ by addition closure, i.e. 
$$\rm r_n,r_{n-1}\in I\ \Rightarrow\ r_{n+1} = \color{#0A0}{q_{n+1}} r_n \color{#C00}{\bf +} r_{n-1} \in I\quad $$
Thus the induction step follows simply because successive remainders are computed from prior remainders $\rm\in I$ using operations that remain in $\rm\,I.$   
Remark $\ $ We can simplify in the ring $\rm\,\Bbb Z.\,$ Integer scalings are  repeated additions or subtractions, so if $\rm\,I\,$ is closed under subtraction then it is also closed under addition and scalings. In group/ring theory language: $\rm\ I\,$ is a ideal of the ring $\rm\,\Bbb Z$ $\!\iff\!$ $\rm I\,$ is an additive subgroup of the additive group $\rm\,\Bbb Z\ $ (since, by the subgroup test, subgroups are precisely the subsets closed under subtraction). 
The essence of the Bezout identity for the gcd is: subgroups of $\rm\,\Bbb Z\,$ are cyclic (or ideals are principal), generated by their least positive element $\rm\,d,\,$ since closed under subtraction implies closed under mod or remainder (obtained by repeated subtraction, i.e. the Division Algorithm). So we conclude $\rm\,d\,$ divides all $\rm\,i\in I\,$ (else $\rm\,i\ mod\ d \in I\,$ is nonzero and smaller than $\rm\,d).\,$ That is essentially the inductive step of the Euclidean algorithm. It generalizes to "Euclidean" rings which enjoy division with "smaller" remainder, e.g. polynomials over a field, where smaller means smaller degree. 
Nonempty subsets of a ring closed under addition and scaling by ring elements are known as ideals. If you study university algebra you will learn that ideals play a fundamental role in number theory and algebra. Ideals abstract the innate structure that governs many proofs in elementary number theory, e.g. denominator ideals and order ideals.
