Euclidean Algorithm/Examples/341 and 527

From ProofWiki
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$


Integer Combination

$31$ can be expressed as an integer combination of $341$ and $527$:

$31 = 2 \times 527 - 3 \times 341$


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