Revision as of 15:50, 22 October 2010

HW1, Chapter 0, Problem 19, MA453, Fall 2008, Prof. Walther

Problem Statement

Could somebody please state the problem?

Discussion

There are a couple ways to go about doing this problem. One of the ways is to use prime factorization. This next part is taken verbatim from Gallian:

By using 0 as an exponent if necessary, we may write $ \displaystyle a = p_1^{m_1} \cdots p_k^{m_k} $ and $ \displaystyle b = p_1^{n_1} \cdots p_k^{n_k} $, where the $ \displaystyle p $'s are distinct primes and the $ \displaystyle m $'s and $ \displaystyle n $'s are nonnegative. Then $ \displaystyle lcm(a, b) = p_1^{s_1} \cdots p_k^{s_k} $, where $ \displaystyle s_i = max(m_i, n_i) $, and $ \displaystyle gcd(a, b) = p_1^{t_1} \cdots p_k^{t_k} $, where $ \displaystyle t_i = min(m_i, n_i) $. Then $ \displaystyle lcm(a, b) \cdot gcd(a, b) = p_1^{m_1 + n_1} \cdots p_k^{m_k + n_k} = ab $.

However, I used the linear combination property of a GCD to solve the problem:

• We know that $ \displaystyle gcd(a, b) = ax + by, x,y\in\mathbb{Z} $. So, $ \displaystyle lcm(a, b)\cdot gcd(a, b) = ax\cdot lcm(a, b) + by\cdot lcm(a, b) $.

• From the definition of a least common multiple, we know that $ \displaystyle a\mid lcm(a, b) $ and $ \displaystyle b\mid lcm(a,b) $. Thus:

$ \displaystyle ax\cdot lcm(a, b) + by\cdot lcm(a, b) $

$ \displaystyle = ab\left(x\cdot \frac{lcm(a, b)}{b}\right) + ab\left(y\cdot \frac{lcm(a, b)}{a}\right) $

$ \displaystyle = ab\left(x\cdot \frac{lcm(a, b)}{b} + y\cdot \frac{lcm(a, b)}{a}\right) $

$ \displaystyle = lcm(a, b)\cdot gcd(a, b) $.

• With this, we know that $ \displaystyle ab\mid lcm(a, b)\cdot gcd(a, b) $, and therefore, $ \displaystyle ab\le lcm(a, b)\cdot gcd(a, b) $.

• It's easy to see that the value $ \displaystyle \frac{ab}{gcd(a, b)} $ is a multiple of $ \displaystyle a $, as well as a multiple of $ \displaystyle b $. So, $ \displaystyle \frac{ab}{gcd(a, b)} $ is a common multiple of $ \displaystyle a $ and $ \displaystyle b $. Since $ \displaystyle lcm(a, b) $ is the least such multiple, it follows that $ \displaystyle lcm(a, b)\le \frac{ab}{gcd(a, b)} $, or $ \displaystyle lcm(a, b)\cdot gcd(a, b)\le ab $.

• Since $ \displaystyle ab\le lcm(a, b)\cdot gcd(a, b) $ and $ \displaystyle ab\ge lcm(a, b)\cdot gcd(a, b) $, we have shown that $ \displaystyle ab = lcm(a, b)\cdot gcd(a, b) $. $ \displaystyle\Box $

This is how I got the answer to #7. Questions? Comments? Criticism? Feel free to edit in a reply.

--Nick Rupley 14:32, 6 September 2008 (UTC)

Back to HW1

Back to MA453 Fall 2008 Prof. Walther