GCD question

**gutnedawg** · Jan 27th 2011, 05:38 PM

if $m>0$

show that

$m(a,b)=(ma,mb)$

I'm told that $(ma,mb) = max + mby = m(ax + by) = m(a,b)$
isn't sufficient... why?

**dwsmith** · Jan 27th 2011, 05:59 PM

Originally Posted by gutnedawg

if $m>0$

show that

$m(a,b)=(ma,mb)$

I'm told that $(ma,mb) = max + mby = m(ax + by) = m(a,b)$
isn't sufficient... why?

$\text{let} \ d=\text{gcd}(ma,mb) \ \ \text{and} \ \ c=\text{gcd}(a,b)$

$d=max+mby \ \ x,y\in\mathbb{Z} \ \ \ mc=maz+mbt \ \ z,t\in\mathbb{Z}$

$d|ma \ \ \text{and} \ \ mc|ma\Rightarrow mc|d$

Now, all you have to do is show d|mc and you can then say d=mc and you are done.

**gutnedawg** · Jan 27th 2011, 06:09 PM

how do I show d|mc?

**dwsmith** · Jan 27th 2011, 06:23 PM

Originally Posted by gutnedawg

how do I show d|mc?

d divides the LHS of $mc=maz+mbt$ ; therefore, d|RHS

**gutnedawg** · Jan 27th 2011, 07:50 PM

but we have shown that mc|d not d|mc so I'm not sure how you come to this conclusion

never mind: since d=(ma,mb) thus d|max+mby for any x,y in Z correct?

**roninpro** · Jan 27th 2011, 08:03 PM

Originally Posted by gutnedawg

if $m>0$

show that

$m(a,b)=(ma,mb)$

I'm told that $(ma,mb) = max + mby = m(ax + by) = m(a,b)$
isn't sufficient... why?

Maybe to answer your original question, the bad part of your proof is here: $m(ax+by)=m(a,b)$ . The only thing that you can conclude about the number $ax+by$ is that it is a multiple of $(a,b)$ , which is a little bit too weak to prove what you want.

**melese** · Jan 28th 2011, 06:53 AM

Originally Posted by gutnedawg

if $m>0$

show that

$m(a,b)=(ma,mb)$

I'm told that $(ma,mb) = max + mby = m(ax + by) = m(a,b)$
isn't sufficient... why?

Let $d=(a,b)$ be the greatest common divisor of $a$ and $b$ . So, $d$ is the smallest positive integer that can be expressed a linear combination of $a$ and $b$ .(Theorem.)

Consider the following linear combinations : $(ma)x+(mb)y=m(ax+by)$ , where $x,y$ are integers.

From the equation we can see that $(ma)x+(mb)y$ is the smallest positive linear combination of $ma$ and $mb$ precisely when $ax+by$ is the smallest positive linear combination of $a$ and $b$ . Applying the theorem we have $(ma,mb)=m(a,b)$ .

Thread: GCD question

LinkBack

Thread Tools

Display

GCD question

Search Tags