# Solution

A number $L$ is called a common multiple of $m$ and $n$ if both $m$ and $n$ divide $L$. The smallest such $L$ is called the least common multiple of m and n and is denoted by $\textrm{lcm} (m,n)$

1. Find the following:
1. lcm (8, 12)
2. lcm (20, 30)
3. lcm (51, 68)
4. lcm (23, 18)
2. Compare the value of $\textrm{lcm} (m,n)$ with the values of $m$, $n$, and gcd($m,n$). In what way are they related?

3. Prove the relationship you found in part (b) always holds.

4. Compute $\textrm{lcm} (301337,307829)$.

5. Find all $m$ and $n$ where $\gcd (m,n) = 18$ and $\textrm{lcm} (m,n) = 720$.

1. 24
2. 60
3. 204
4. 414
1. It appears that the product of the lcm and the gcd always equals $mn$.

2. Let $p_1,p_2,p_3, ...$ be the primes: 2, 3, 5, ..., in order of magnitude. Let $p_r$ be the largest prime that divides either $m$ or $n$.

Then we can find write a prime factorization for both $m$ and $n$ in the following way: $m = p^{m_1}_1 p^{m_2}_2 \cdots p^{m_r}_r$ and $n = p^{n_1}_1 p^{n_2}_2 \cdots p^{n_r}_r$. Note, that some primes may not divide $m$ or $n$, so some of the exponents may be zero.

It should be clear that $$\gcd(m,n) = p^{\min(m_1,n_1)}_1 p^{\min(m_2,n_2)}_2 \cdots$$ $$\textrm{lcm}(m,n) = p^{\max(m_1,n_1)}_1 p^{\max(m_2,n_2)}_2 \cdots$$

As such, the product of the gcd and lcm is
\begin{align} \gcd \cdot \textrm{lcm} &= p^{\min(m_1,n_1)+\max(m_1,n_1)}_1 p^{\min(m_2,n_2)+\max(m_2,n_2)}_2 \cdots\\ &= p^{m_1+n_1}_1 p^{m_2+n_2}_2 \cdots\\ &= (p^{m_1}_1 p^{m_2}_2 \cdots) (p^{n_1}_1 p^{n_2}_2 \cdots)\\ &= mn \end{align}

3. 171460753

4. (144,90) or (720,18)