Exercises - The GCD and Euclidean Algorithm

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

    1. gcd(12345,67890)
    2. gcd(54321,9876)


    1. $\displaystyle{\begin{align*} 67890 &= 5 \cdot 12345 + 6165\\ 12345 &= 2 \cdot 6165 + \fbox{15} \leftarrow \textrm{gcd}\\ 6165 &= 411 \cdot 15 + 0 \end{align*}}$


    2. $\displaystyle{\begin{align*} 54321 &= 5 \cdot 9876 + 4941\\ 9876 &= 1 \cdot 4941 + 4935\\ 4941 &= 1 \cdot 4935 + 6\\ 4935 &= 822 \cdot 6 + \fbox{3} \leftarrow \textrm{gcd}\\ 6 &= 2 \cdot 3 + 0 \end{align*}}$

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

      1. 24
      2. 60
      3. 204
      4. 414

    2. It appears that the product of the lcm and the gcd always equals $mn$.

    3. 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}$$

    4. 171460753

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

  3. Prove for all positive integers $a$ and $b$, it must be the case that $\textrm{gcd}(a+b,a-b) \ge \textrm{gcd}(a,b)$.

    Let $d = \textrm{gcd}(a,b)$, can you argue $d | a+b$ and $d | a-b$?

  4. 🔎 In number theory we are often curious about the greatest common divisors of two integers of interest. In this spirit, let us ask the question "Can anything interesting be said about the gcd of any two Fibonacci numbers?" Recall the $n^{th}$ Fibonacci number is defined by $f_1 = 1$, $f_2 = 1$, and $f_n = f_{n-1} + f_{n-2}$ for $n \gt 2$. Experimenting with several pairs of Fibonacci numbers should lead one to make the following startling conjecture:

    $$\textrm{gcd}(f_m,f_n) = f_{\textrm{gcd}(m,n)}$$

    If one knows $\textrm{gcd}(a,b)$, what is $\textrm{gcd}(a-b,b)$?