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

• Jan 7th 2010, 09:39 PM
kingwinner
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! :)
• Jan 7th 2010, 09:57 PM
Drexel28
Quote:

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}$
• Jan 8th 2010, 02:37 AM
Shanks
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.
• Jan 9th 2010, 02:32 PM
kingwinner
Quote:

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?
• Jan 9th 2010, 02:37 PM
Drexel28
Quote:

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.