# Thread: gcd(ma,mb) = m gcd(a,b)

1. ## gcd(ma,mb) = m gcd(a,b)

Theorem:
For any natural number m, gcd(ma,mb) = m gcd(a,b)

Proof:
Let N={natural numbers}
By another theorem, we know that
gcd(ma,mb)=min({m(ax)+m(by): x,y E Z} ∩ N)
=m * min({ax+by: x,y E Z} ∩ N)
=m * gcd(a,b)
===========================

I don't understand the step
min({m(ax)+m(by): x,y E Z} ∩ N) = m * min({ax+by: x,y E Z} ∩ N).
Why is this true? Can someone please explain this?

Thanks for any help!

2. Originally Posted by kingwinner
Theorem:
For any natural number m, gcd(ma,mb) = m gcd(a,b)

Proof:
Let N={natural numbers}
By another theorem, we know that
gcd(ma,mb)=min({m(ax)+m(by): x,y E Z} ∩ N)
=m * min({ax+by: x,y E Z} ∩ N)
=m * gcd(a,b)
===========================

I don't understand the step
min({m(ax)+m(by): x,y E Z} ∩ N) = m * min({ax+by: x,y E Z} ∩ N).
Why is this true? Can someone please explain this?

Thanks for any help!
Suppose that $\tau=\min\left\{max+mby:x,y\in\mathbb{Z}\right\}\c ap \mathbb{N}$, then $\tau=ma\tilde{x}+mb\tilde{y}$ for some $\tilde{x},\tilde{y}\in\mathbb{Z}$. I claim that $a\tilde{x}+a\tilde{y}=\min\left\{ax+by:x,y\in\math bb{Z}\right\}\cap\mathbb{N}$. To see this assume it was false. Then there exists some $ax'+by'\in\left\{ax+by:x,y\in\mathbb{Z}\right\}\ca p\mathbb{N}$ such that $ax'+by'\leqslant a\tilde{x}+b\tilde{y}$ but since $m\in\mathbb{N}$ we see that this implies $max'+mby'\leqslant ma\tilde{x}+mb\tilde{y}$ which contradicts the minimality of $ma\tilde{x}+mb\tilde{y}$. Thus, we have that $\min\left\{max+mby:x,y\in\mathbb{Z}\right\}\cap\ma thbb{N}=ma\tilde{x}+mb\tilde{y}=m\cdot\min\left\{a x+by:x,y\in\mathbb{Z}\right\}\cap\mathbb{N}$

3. Definition of gcd by linear combination:
let a and b are two integers, then gcd(a,b) is the smallest positive integer which can be written as a linear combination of a and b over Z, that is, there exist integers x and y such that gcd(a,b)=ax+by.
This is why the equality $gcd(a,b)=min\{\{ax+by:x,y\in Z\}\cap N\}$ holds.

4. Originally Posted by Drexel28
Suppose that $\tau=\min\left\{max+mby:x,y\in\mathbb{Z}\right\}\c ap \mathbb{N}$, then $\tau=ma\tilde{x}+mb\tilde{y}$ for some $\tilde{x},\tilde{y}\in\mathbb{Z}$. I claim that $a\tilde{x}+a\tilde{y}=\min\left\{ax+by:x,y\in\math bb{Z}\right\}\cap\mathbb{N}$. To see this assume it was false. Then there exists some $ax'+by'\in\left\{ax+by:x,y\in\mathbb{Z}\right\}\ca p\mathbb{N}$ such that $ax'+by'\leqslant a\tilde{x}+b\tilde{y}$ but since $m\in\mathbb{N}$ we see that this implies $max'+mby'\leqslant ma\tilde{x}+mb\tilde{y}$ which contradicts the minimality of $ma\tilde{x}+mb\tilde{y}$. Thus, we have that $\min\left\{max+mby:x,y\in\mathbb{Z}\right\}\cap\ma thbb{N}=ma\tilde{x}+mb\tilde{y}=m\cdot\min\left\{a x+by:x,y\in\mathbb{Z}\right\}\cap\mathbb{N}$
Thanks, that makes sense.

But is there any "intuitive" way to understand the reason why we can factor the "m" out of the min?

5. Originally Posted by kingwinner
Thanks, that makes sense.

But is there any "intuitive" way to understand the reason why we can factor the "m" out of the min?
What I said is very intuitive. It is just shrouded in formal language. Basically, the reason why we can factor the $m$ out is that it doesn't contribute to the minimum. So, multiplying by a constant will not change the minimum of a set...except for multiplying it by the constant.

Think about it like this. (this is really informal, and kind of incorrect)

We can think about the one set as

$ax_1+by_1. Now, if I multiply by $m$ I get $amx_1+bmy_1 so that the minimum of the second set is clearly going to just be $m$ times the mimum of the first set.

,

,

### gcd(ma,mb)=m×gcd(a,b)

Click on a term to search for related topics.