Proof $ GCD(a,b) = GCD(a, b-a) = GCD (a, r_b) $

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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