Euclidean Algorithm/Examples/341 and 527/Proof
< Euclidean Algorithm | Examples | 341 and 527
Jump to navigation
Jump to search
Examples of Use of Euclidean Algorithm
The GCD of $341$ and $527$ is found to be:
- $\gcd \set {341, 527} = 31$
Proof
| \(\text {(1)}: \quad\) | \(\ds 527\) | \(=\) | \(\ds 1 \times 341 + 186\) | |||||||||||
| \(\text {(2)}: \quad\) | \(\ds 341\) | \(=\) | \(\ds 1 \times 186 + 155\) | |||||||||||
| \(\text {(3)}: \quad\) | \(\ds 186\) | \(=\) | \(\ds 1 \times 155 + 31\) | |||||||||||
| \(\ds 155\) | \(=\) | \(\ds 5 \times 31\) |
Thus:
- $\gcd \set {341, 527} = 31$
$\blacksquare$
Sources
- 1971: George E. Andrews: Number Theory ... (previous) ... (next): $\text {2-2}$ Divisibility: Example $\text {2-7}$