Euclidean Algorithm/Examples/341 and 527/Integer Combination

From ProofWiki
Jump to navigation Jump to search

Examples of Use of Euclidean Algorithm

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

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


Note also that:

$31 = 14 \times 341 = 9 \times 527$

and:

$31 = 13 \times 527 - 20 \times 341$


Proof

From Euclidean Algorithm: $341$ and $527$ we have:

$\gcd \set {341, 527} = 31$


Then we have:

\(\ds 31\) \(=\) \(\ds 186 - 1 \times 155\) from $(3)$
\(\ds \) \(=\) \(\ds 186 - 1 \times \paren {341 - 1 \times 186}\) from $(2)$
\(\ds \) \(=\) \(\ds 2 \times 186 - 1 \times 341\)
\(\ds \) \(=\) \(\ds 2 \times \paren {527 - 1 \times 341} - 1 \times 341\) from $(1)$
\(\ds \) \(=\) \(\ds 2 \times 527 - 3 \times 341\)

$\blacksquare$


Sources