Euclidean Algorithm/Examples/12321 and 8658

Examples of Use of Euclidean Algorithm

The GCD of $12321$ and $8658$ is:

$\gcd \set {12321, 8658} = 333$

Proof

\(\text {(1)}: \quad\)

\(\ds 12321\)

\(=\)

\(\ds 1 \times 8658 + 3663\)

\(\text {(2)}: \quad\)

\(\ds 8653\)

\(=\)

\(\ds 2 \times 3663 + 1332\)

\(\text {(3)}: \quad\)

\(\ds 3663\)

\(=\)

\(\ds 2 \times 1332 + 999\)

\(\text {(4)}: \quad\)

\(\ds 1332\)

\(=\)

\(\ds 1 \times 999 + 333\)

\(\text {(5)}: \quad\)

\(\ds 999\)

\(=\)

\(\ds 3 \times 333\)

Thus:

$\gcd \set {12321, 8658} = 333$

$\blacksquare$

Sources

• 1971: George E. Andrews: Number Theory ... (previous) ... (next): $\text {2-2}$ Divisibility: Exercise $1 \ \text{(c)}$