Solution

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*}}$