Euclidean Algorithm/Examples/595 and 721

Examples of Use of Euclidean Algorithm

The GCD of $595$ and $721$ is found to be:

$\gcd \set {595, 721} = 7$

Proof

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

\(\ds 721\)

\(=\)

\(\ds 1 \times 595 + 126\)

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

\(\ds 595\)

\(=\)

\(\ds 5 \times 126 - 35\)

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

\(\ds 126\)

\(=\)

\(\ds 4 \times 35 - 14\)

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

\(\ds 35\)

\(=\)

\(\ds 2 \times 14 + 7\)

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

\(\ds 14\)

\(=\)

\(\ds 2 \times 7\)

Thus:

$\gcd \set {595, 721} = 7$

$\blacksquare$

Sources

• 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): Euclidean algorithm
• 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): Euclidean algorithm