TAOCP 4.5.2 Exercise 9

We are asked to compute $\gcd(31408, 2718)$ using **Algorithm B**, and then to find integers $m$ and $n$ such that $31408 \, m + 2718 \, n = \gcd(31408, 2718)$ using **Algorithm X**.

taocpmathematicsalgorithmsvolume-2medium

Section 4.5.2: The Greatest Common Divisor

Exercise 9. [18] Using Algorithm B and hand calculation, find gcd(31408, 2718). Also find integers $m$ and $n$ such that $31408n + 2718n = \gcd(31408, 2718)$, using Algorithm X.

Verified: yes
Solve time: 3m

Solution

We are asked to compute $\gcd(31408, 2718)$ using Algorithm B, and then to find integers $m$ and $n$ such that

$31408 , m + 2718 , n = \gcd(31408, 2718)$

using Algorithm X.

We proceed step by step, following Knuth's notation in Section 4.5.2.

Step 1: Apply Algorithm B

Algorithm B performs Euclid's algorithm by repeated remainder computation. Let $u = 31408$, $v = 2718$.

  1. Compute $r_1 = u \bmod v = 31408 \bmod 2718$.

Divide $31408$ by $2718$: $2718 \cdot 11 = 29898$, remainder $31408 - 29898 = 1510$.

So $r_1 = 1510$. 2. Set $u \leftarrow v = 2718$, $v \leftarrow r_1 = 1510$. Compute $r_2 = 2718 \bmod 1510 = 2718 - 1510 = 1208$. 3. Set $u \leftarrow 1510$, $v \leftarrow 1208$. Compute $r_3 = 1510 \bmod 1208 = 1510 - 1208 = 302$. 4. Set $u \leftarrow 1208$, $v \leftarrow 302$. Compute $r_4 = 1208 \bmod 302$. Since $302 \cdot 4 = 1208$, remainder $r_4 = 0$.

Algorithm B terminates, and the last nonzero remainder is $v = 302$. Therefore

$\gcd(31408, 2718) = 302. \quad \boxed{302}$

Step 2: Apply Algorithm X (Extended Euclidean Algorithm)

Algorithm X finds integers $m$ and $n$ such that

$31408 , m + 2718 , n = 302.$

We compute stepwise using the sequence of divisions from Step 1.

  1. From Step 1, the remainders satisfy:

$$ \begin{aligned} 31408 &= 2718 \cdot 11 + 1510 \ 2718 &= 1510 \cdot 1 + 1208 \ 1510 &= 1208 \cdot 1 + 302 \ 1208 &= 302 \cdot 4 + 0 \end{aligned} $$

  1. Back-substitute to express $302$ as a linear combination of $31408$ and $2718$:
  • From the third equation:

$302 = 1510 - 1208 \cdot 1.$

  • From the second equation: $1208 = 2718 - 1510$, so

$$ 302 = 1510 - (2718 - 1510) = 1510 - 2718 + 1510 = 2 \cdot 1510 - 2718. $$

  • From the first equation: $1510 = 31408 - 2718 \cdot 11$, so

$$ 302 = 2(31408 - 2718 \cdot 11) - 2718 = 2 \cdot 31408 - 22 \cdot 2718 - 2718 = 2 \cdot 31408 - 23 \cdot 2718. $$

Thus one solution is

$$ m = 2, \quad n = -23. $$

Step 3: Verification

$$ 31408 \cdot 2 + 2718 \cdot (-23) = 62816 - 62414 = 302, $$

which agrees with the gcd computed in Step 1.

This completes the solution. ∎

$$ \boxed{\gcd(31408, 2718) = 302, \quad m = 2, , n = -23} $$