# 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.

## 3 Answers

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.

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$).

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.$