Euclidean Algorithm/Examples/527 and 765

Examples of Use of Euclidean Algorithm

The GCD of $527$ and $765$ is:

$\gcd \set {527, 765} = 17$

Proof

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

\(\ds 765\)

\(=\)

\(\ds 1 \times 527 + 238\)

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

\(\ds 527\)

\(=\)

\(\ds 2 \times 238 + 51\)

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

\(\ds 238\)

\(=\)

\(\ds 4 \times 51 + 34\)

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

\(\ds 51\)

\(=\)

\(\ds 1 \times 34 + 17\)

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

\(\ds 34\)

\(=\)

\(\ds 2 \times 17\)

Thus:

$\gcd \set {527, 765} = 17$

$\blacksquare$

Sources

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