Euclidean Algorithm/Examples/1769 and 2378/Proof
< Euclidean Algorithm | Examples | 1769 and 2378
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$