Euclidean Algorithm/Least Absolute Remainder/Examples/12378 and 3054

Examples of Use of Euclidean Algorithm: Least Absolute Remainder Variant

The GCD of $12378$ and $3054$ is:

$\gcd \set {12378, 3054} = 6$

and takes $4$ division operations to get there.

$6$ can be expressed as an integer combination of $12378$ and $3054$:

$6 = 132 \times 12378 - 535 \times 3054$

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

$\ds 12378$

$=$

$\ds 4 \times 3054 + 162$

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

$\ds 3054$

$=$

$\ds 19 \times 162 - 24$

$\text {(3)}: \quad$

$\ds 162$

$=$

$\ds 7 \times 24 - 6$

$\text {(4)}: \quad$

$\ds 24$

$=$

$\ds \paren {-4} \times \paren {-6} + 0$

Thus:

$\gcd \set {12378, 3054} = 6$

As can be seen, it takes $4$ division operations.

$\blacksquare$

1980: David M. Burton: Elementary Number Theory (revised ed.) ... (previous) ... (next): Chapter $2$: Divisibility Theory in the Integers: $2.3$ The Euclidean Algorithm