Euclidean Algorithm/Examples/361 and 1178

Examples of Use of Euclidean Algorithm

The GCD of $361$ and $1178$ is:

$\gcd \set {361, 1178} = 19$

Proof

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

\(\ds 1178\)

\(=\)

\(\ds 3 \times 361 + 95\)

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

\(\ds 361\)

\(=\)

\(\ds 3 \times 95 + 76\)

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

\(\ds 95\)

\(=\)

\(\ds 1 \times 76 + 19\)

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

\(\ds 76\)

\(=\)

\(\ds 4 \times 19\)

Thus:

$\gcd \set {361, 1178} = 19$

$\blacksquare$

Sources

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