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)