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

Problem Statement

Could somebody please state the problem?

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)