Proof $ GCD(a,b) = GCD(a, b-a) = GCD (a, r_b) $ let $a,b \in \mathbb{N}$ and a < b.
let $r_b$ the rest when dividing b through a.
(1) If $r_b$ is the rest, then there exists a q so that $ b = q*a + r_b $.
(2) Now I show: $gcd(a,b) = gcd(a, b-a)$.
(2.1) let d := gcd(a,b), this means d|a and d|b. This means a = nd, b=md (with m > n since b > a). Then b-a = md -nd = (m-n)d, where (m-n)>0. Therefore d|b-a
(2.2) let g := gcd(a,b-a), this means g|a and g|b-a. This means a = xg, b-a=yg. Then b = (b-a)+a = xg +yg = (x+y)g. Therefore g|b.
(2.3) Together we have d|a, d|b, d|b-a. And g|a, g|b, g|b-a.
Now, since I supposed d and g to be the GREATEST common divisor, it must be g = d and everything is shown.
I hope so.
(3) Now I show $gcd(a,b) = gcd(a, r_b)$.
As I have shown in (2-2.3) I have
$gcd(a,b) = gcd(a, b-a) = gcd(a, [b-a]-a) = ...$. If doing this q-times, then I have
$gcd(a,b) = ... = gcd(a, b-qa)$. Since $ b = qa + r_b$ I have $b-qa = r_b$.
I'm pretty sure this should hold, however I'd like to do it by induction, if possible. Is there a way to show this more 'mathematically' ?
Kind Regards,
K.
 A: If you want to prove your statement by induction, it is best to see where you used a step that is "induction like". It usually occurs where you say something like "if I do this $k$-times".
In your case, you want to show that $GCD(a,b) = GCD(a, b-k\cdot a)$ for any value of the integer $k$. If you prove this, you can then plug in $k=q$ and get $GCD(a,b) = GCD(a,b-qa)=GCD(a,r_b)$.
The proof by induction should not cause you much trouble, since it is just formalizing the idea you already know is true.
A: To do it by induction, all you have to do is pose [b-a]=$b1$. if q=1, then you are done since b-a=$b_1$=$r_b$. If q>1, then b-a=$b_1$ > a; as you have shown before gcd(a,$b_1$)=gcd(a,$b_1$-a) for $b_1$ > a. Then pose again $b_1$-a=$b_2$. if q=2, then $b_1$-a=$b_2$=$rb$. If not, then $b_1$-a=$b_2$ > a. Assume gcd(a,$b_q-$1) = gcd(a,$b_q-$1 - a). By the same reasoning, pose $b_q$ = $b_q-$1 - a=$r_b$ and conclude that gcd(a,b)=gcd(a,$r_b$).
A: This does not use induction, but the result follows nicely once you show that $(a,b)=(b,r)$ if $a=bq+r$ with $0\leq r<b.$
