TAOCP 1.1 Exercise 4

Exercise 4. [16] What is the greatest common divisor of 2166 and 6099?

Verified: yes
Solve time: 1m11s

Apply Algorithm E to $m = 6099$ and $n = 2166$.

At step E1,

$$ 6099 = 2 \cdot 2166 + 1767, $$

so $r \leftarrow 1767$. Since $r \ne 0$, step E3 sets

$$ m \leftarrow 2166, \qquad n \leftarrow 1767. $$

Next,

$$ 2166 = 1 \cdot 1767 + 399, $$

so $r \leftarrow 399$, and step E3 gives

$$ m \leftarrow 1767, \qquad n \leftarrow 399. $$

Next,

$$ 1767 = 4 \cdot 399 + 171, $$

so $r \leftarrow 171$, and step E3 gives

$$ m \leftarrow 399, \qquad n \leftarrow 171. $$

Next,

$$ 399 = 2 \cdot 171 + 57, $$

so $r \leftarrow 57$, and step E3 gives

$$ m \leftarrow 171, \qquad n \leftarrow 57. $$

Finally,

$$ 171 = 3 \cdot 57 + 0. $$

At step E2, since $r = 0$, the algorithm terminates and returns $n = 57$.

Therefore the greatest common divisor of $2166$ and $6099$ is

$$ \boxed{57} $$