Question about proof of $\gcd(a,b)=\gcd(b,r)$

Question

I've seen the following proof of the basic result that

If $a=kb+r$, then $\gcd(a,b)=\gcd(b,r)$, for $a,b,r \in\mathbb{Z}$ and $0 \leq r < |b|$.

Proof: By Bézout's identity $\gcd(a,b)=sa+tb$, for some $s,t \in \mathbb{Z}$. Then $\gcd(a,b)=s(kb+r)+tb = (sk+t)b+sr=\gcd(b,r)$.

What I don't understand is why $(sk+t)b+sr$ is exactly $\gcd(b,r)$ and not just some multiple of $\gcd(b,r)$. How can that be seen?

Answer 1

That property becomes clear considering that for any divisor $d$, such that $d|a$ and $d|b$, if $a=kb+r$ then

$$d|kb+r\iff d|r$$

and thus (a,b) and (b,r) share the same set of common divisors and therefore

$$\gcd(a,b)=\gcd(b,r)$$

Answer 2

gcd(a,b)=sa+tb. This implies gcd(a,b)=$min_{s,t} (sa+tb) (sa+sb≧1)$. $gcd(a,b)=min_{s,t}(sa+tb)=min_{s,t}(s(bk+r)+tb)=min_{s,t}((sk+t)b+sr)$ .sk+t and s can take any Integers independently.So let sk+t=s' and s=t'.Then gcd(a,b)=$min_{s',t'}(s'b+t'r)=gcd(b,r)$.

Answer 3

Set $d:=\gcd(a,b)$. Then with $c:=b/d$ we have $d\mid a = kb+r = kcd+r$ and thus $d\mid (a-kcd) = r$. Thus $\gcd(b,r)$ is some multiple of $d$.

Now suppose there is some $j>1$ such that $jd \mid r$ and $jd \mid b$. Then also $jd\mid kb+r = a$, which would contradict $d=\gcd(a,b)$

Thus $\gcd(b,r)=\gcd(a,b)$.

Answer 4

You're right. $\gcd(a,b)$ is the smallest positive integer that can be expressed as $as+tb$ where $s,t \in \mathbb Z$. Since $as+tb=s(kb+r)+tb = (sk+t)b+sr$, then $\gcd(b,r) \le \gcd(a,b)$.

But, since $ub + vr = ub + v(a-kb) = va + (u-vk)b$, we see that $\gcd(a,b) \le \gcd(b,r)$.

Hence $\gcd(a,b) = \gcd(b,r)$.

Answer 5

We do not need the Bezout identity for this. In fact this is usually used in order to prove the Bezout identity. (See footnote.)

Let all values be integers.

A linear combination of $p$ and $q$ is $px+qy$ for some (any) $x,y.$ Any common divisor of $p$ and $q$ is a divisor of every linear combination of $p$ and $q.$ Because if $p=p'n$ and $q=q'n$ then $px+qy=n(p'x+q'y).$

If $a=kb+r$ then:

(i). $a$ is a linear combination of $b$ and $r.$ So every common divisor of $b$ and $r$ is a divisor of $a.$

$\bullet \;$ So every common divisor of $b$ and $r$ is also a common divisor of $b$ and $a.$

(ii). $r=a-kb$ is a linear combination of $a$ and $b.$ So every common divisor of $b$ and $a$ is a divisor of $r.$

$\bullet \bullet \;$ So every common divisor of $b$ and $a$ is also a common divisor of $b$ and $r$.

From $\bullet$ and $\bullet \bullet,$ the set of common divisors of $b$ and $r$ is the same as the the set of common divisors of $b$ and $a.$ So the greatest member of this set is $\gcd(b,r)$ and is also $\gcd(b,a).$

Footnote. Let $L(p,q)$ be the set of all linear combinations of $p,q.$ Observe that if $r,s \in L(p,q)$ and $t\in L(r,s)$ then $t\in L(p,q).$ Example: We have $39-2(17)=5$ and $17-3(5)=2$ and $5-2(2)=1$. Now $5$ and $17$ are in $L(39,17)$ and $2\in L(5,17),$ therefore $2\in L(39,17).$ So, since $5$ and $2$ are in $L(39,17)$ and $1\in L(5,2),$ therefore $1\in L(39,17).$ That is, there exist $x,y\in \Bbb Z$ such that $1=39x+17y .$