Euclidean Algorithm/Examples/1769 and 2378

Examples of Use of Euclidean Algorithm

The GCD of $1769$ and $2378$ is found to be:

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

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

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

$\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$