# Euclidean Algorithm/Examples/12378 and 3054/Integer Combination

## Examples of Use of Euclidean Algorithm

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

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

Note also that:

$6 = 3186 \times 12378 - 12913 \times 3054$

by adding $3054 \times 12378$ to both sides.

## Proof

From Euclidean Algorithm: $12378$ and $3054$ we have:

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

Then we have:

 $\ds 6$ $=$ $\ds 24 - 1 \times 18$ from $(5)$ $\ds$ $=$ $\ds 24 - 1 \times \paren {138 - 5 \times 24}$ from $(4)$ $\ds$ $=$ $\ds 6 \times 24 - 1 \times 138$ $\ds$ $=$ $\ds 6 \times \paren {162 - 1 \times 138} - 1 \times 138$ from $(3)$ $\ds$ $=$ $\ds 6 \times 162 - 7 \times 138$ $\ds$ $=$ $\ds 6 \times 162 - 7 \times \paren {3054 - 18 \times 162}$ from $(2)$ $\ds$ $=$ $\ds 132 \times 162 - 7 \times 3054$ $\ds$ $=$ $\ds 132 \times \paren {12378 - 4 \times 3054} - 7 \times 3054$ from $(1)$ $\ds$ $=$ $\ds 132 \times 12378 - 535 \times 3054$

$\blacksquare$