Exercises - The GCD and the Euclidean Algorithm

  1. Use the Euclidean algorithm to compute each of the following gcd's.  

    1. gcd(12345,67890)
    2. gcd(54321,9876)
  2. 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$.

◆ ◆ ◆