Results 1 to 5 of 5

- Jan 7th 2010, 10:39 PM #1

- Joined
- Jan 2009
- Posts
- 404

## 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, 10:57 PM #2

- Jan 8th 2010, 03:37 AM #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 holds.

- Jan 9th 2010, 03:32 PM #4

- Joined
- Jan 2009
- Posts
- 404

- Jan 9th 2010, 03:37 PM #5
What I said is very intuitive. It is just shrouded in formal language. Basically, the reason why we can factor the 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

. Now, if I multiply by I get so that the minimum of the second set is clearly going to just be times the mimum of the first set.

Click on a term to search for related topics.