Euclidean Algorithm/Examples/132 and 473

Examples of Use of Euclidean Algorithm

The GCD of $132$ and $473$ is:

$\gcd \set {132, 473} = 11$

Proof

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

\(\ds 473\)

\(=\)

\(\ds 3 \times 132 + 77\)

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

\(\ds 132\)

\(=\)

\(\ds 1 \times 77 + 55\)

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

\(\ds 77\)

\(=\)

\(\ds 1 \times 55 + 22\)

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

\(\ds 55\)

\(=\)

\(\ds 2 \times 22 + 11\)

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

\(\ds 22\)

\(=\)

\(\ds 2 \times 11\)

Thus:

$\gcd \set {132, 473} = 11$

$\blacksquare$

Sources

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