# 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 $\displaystyle \tau=\min\left\{max+mby:x,y\in\mathbb{Z}\right\}\c ap \mathbb{N}$, then $\displaystyle \tau=ma\tilde{x}+mb\tilde{y}$ for some $\displaystyle \tilde{x},\tilde{y}\in\mathbb{Z}$. I claim that $\displaystyle 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 $\displaystyle ax'+by'\in\left\{ax+by:x,y\in\mathbb{Z}\right\}\ca p\mathbb{N}$ such that $\displaystyle ax'+by'\leqslant a\tilde{x}+b\tilde{y}$ but since $\displaystyle m\in\mathbb{N}$ we see that this implies $\displaystyle max'+mby'\leqslant ma\tilde{x}+mb\tilde{y}$ which contradicts the minimality of $\displaystyle ma\tilde{x}+mb\tilde{y}$. Thus, we have that $\displaystyle \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 $\displaystyle gcd(a,b)=min\{\{ax+by:x,y\in Z\}\cap N\}$ holds.

4. Originally Posted by Drexel28
Suppose that $\displaystyle \tau=\min\left\{max+mby:x,y\in\mathbb{Z}\right\}\c ap \mathbb{N}$, then $\displaystyle \tau=ma\tilde{x}+mb\tilde{y}$ for some $\displaystyle \tilde{x},\tilde{y}\in\mathbb{Z}$. I claim that $\displaystyle 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 $\displaystyle ax'+by'\in\left\{ax+by:x,y\in\mathbb{Z}\right\}\ca p\mathbb{N}$ such that $\displaystyle ax'+by'\leqslant a\tilde{x}+b\tilde{y}$ but since $\displaystyle m\in\mathbb{N}$ we see that this implies $\displaystyle max'+mby'\leqslant ma\tilde{x}+mb\tilde{y}$ which contradicts the minimality of $\displaystyle ma\tilde{x}+mb\tilde{y}$. Thus, we have that $\displaystyle \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 $\displaystyle 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

$\displaystyle ax_1+by_1<ax_2+by_2<\cdots$. Now, if I multiply by $\displaystyle m$ I get $\displaystyle amx_1+bmy_1<amx_2+bmy_2<\cdots$ so that the minimum of the second set is clearly going to just be $\displaystyle m$ times the mimum of the first set.

,

,

,

,

,

,

,

,

,

,

,

# show that (ma,mb) =m(a,b) ,where m is a positive integer

Click on a term to search for related topics.