Euclidean Algorithm/Examples/129 and 301

Examples of Use of Euclidean Algorithm

The GCD of $129$ and $301$ is found to be:

$\gcd \set {129, 301} = 43$

Hence $43$ can be expressed as an integer combination of $129$ and $301$:

$43 = 1 \times 301 - 2 \times 129$

Proof

\(\text {(1)}: \quad\)

\(\ds 301\)

\(=\)

\(\ds 2 \times 129 + 43\)

\(\text {(2)}: \quad\)

\(\ds 129\)

\(=\)

\(\ds 3 \times 43\)

Thus:

$\gcd \set {129, 301} = 43$

Then we have:

\(\ds 43\)

\(=\)

\(\ds 301 - 2 \times 129\)

from $(1)$

$\blacksquare$

Sources

• 1971: George E. Andrews: Number Theory ... (previous) ... (next): $\text {2-2}$ Divisibility: Exercise $3$