Euclidean Algorithm/Examples/1769 and 2378/Integer Combination

From ProofWiki
Jump to navigation Jump to search

Examples of Use of Euclidean Algorithm

$6$ can be expressed as an integer combination of $1769$ and $2378$:

$29 = 39 \times 1769 - 29 \times 2378$


Proof

From Euclidean Algorithm: $1769$ and $2378$ we have:

\(\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\)

and so:

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


Then we have:

\(\ds 29\) \(=\) \(\ds 551 - 9 \times 58\) from $(4)$
\(\ds \) \(=\) \(\ds 551 - 9 \times \paren {609 - 1 \times 551}\) from $(3)$
\(\ds \) \(=\) \(\ds 10 \times 551 - 9 \times 609\) simplifying
\(\ds \) \(=\) \(\ds 10 \times \paren {1769 - 2 \times 609} - 9 \times 609\) from $(2)$
\(\ds \) \(=\) \(\ds 10 \times 1769 - 29 \times 609\) simplifying
\(\ds \) \(=\) \(\ds 10 \times 1769 - 29 \times \paren {2378 - 1 \times 1769}\) from $(1)$
\(\ds \) \(=\) \(\ds 39 \times 1769 - 29 \times 2378\) simplifying

$\blacksquare$


Sources