gcd(a+bm,b)=gcd(a,b)

In this video, I prove that $$\gcd(a+bm,b)=\gcd(a,b)$$. I use the definition that the $$\gcd(a,b)=d$$ where if $$k\mid a$$ and $$k\mid b$$, then $$k\mid d$$.

[prathikkannan]

We first prove a lemma that will be important.

By division algorithm we know a = bq + r for some 0 <= r < b.

We now claim that gcd(a, b) = gcd(b, r).

Suppose we have some k s.t k|a and k|b, then k|a - bq = r.

Conversely if k|b, and k|r, then k|bq + r = a.

Thus we see the set of common divisors for gcd(a, b) and gcd(b, r) are equal, and hence they must be the same.

So now given a, b, we set up a = bq + r, and since we know gcd(a, b) = gcd(b, r), we substitute to get gcd(a, b) = gcd(a-bq, b).

[muhammedabdullvek]

you should've said that n is the gcd of a and a+bm. After conclude that d | n and n | d, so n = d.