Euclidean Algorithm/Examples/156 and 1740

Examples of Use of Euclidean Algorithm

The GCD of $156$ and $1740$ is:

$\gcd \set {156, 1740} = 12$

Proof

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

\(\ds 1740\)

\(=\)

\(\ds 11 \times 156 + 24\)

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

\(\ds 156\)

\(=\)

\(\ds 6 \times 24 + 12\)

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

\(\ds 24\)

\(=\)

\(\ds 2 \times 12\)

Thus:

$\gcd \set {156, 1740} = 12$

$\blacksquare$

Sources

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