Euclidean Algorithm/Examples/1769 and 2378/Proof

From ProofWiki
Jump to navigation Jump to search

Examples of Use of Euclidean Algorithm

The GCD of $1769$ and $2378$ is found to be:

$\gcd \set {1769, 2378} = 29$


Proof

\(\text {(1)}: \quad\) \(\ds 2378\) \(=\) \(\ds 1 \times 1769 + 609\)
\(\text {(2)}: \quad\) \(\ds 1769\) \(=\) \(\ds 2 \times 609 + 551\)
\(\text {(3)}: \quad\) \(\ds 609\) \(=\) \(\ds 1 \times 551 + 58\)
\(\text {(4)}: \quad\) \(\ds 551\) \(=\) \(\ds 9 \times 58 + 29\)
\(\text {(5)}: \quad\) \(\ds 58\) \(=\) \(\ds 2 \times 29\)


Thus:

$\gcd \set {1769, 2378} = 29$

$\blacksquare$