# 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$.

◆ ◆ ◆