# Euclidean Algorithm/Construction of Integer Combination

## Construction of Integer Combination from Euclidean Algorithm

Having determined the GCD of $a$ and $b$ using the Euclidean Algorithm, we are now in a position to find a solution to $\gcd \set {a, b} = x a + y b$ for $x$ and $y$.

By Bézout's Identity it is always possible to find such an $x, y \in \Z$.

Working back through the equations generated during the course of working the Euclidean Algorithm, we get:

 $\ds \gcd \set {a, b}$ $=$ $\ds r_n$ $\ds$ $=$ $\ds r_{n - 2} - q_n r_{n - 1}$ $\ds$ $=$ $\ds r_{n - 2} - q_n \paren {r_{n - 3} - q_{n - 1} r_{n - 2} }$ $\ds$ $=$ $\ds \paren {1 + q_n q_{n - 1} } r_{n - 2} - q_n r_{n - 3}$ $\ds$ $=$ $\ds \paren {1 + q_n q_{n - 1} } \paren {r_{n - 4} - q_{n - 2} r_{n - 3} } - q_n r_{n - 3}$

... and so on. The algebra gets messier the further up the tree you go, and is not immediately enlightening.

Thus eventually we arrive at $\gcd \set {a, b} = x a + y b$ where $x$ and $y$ are numbers made up from some algebraic cocktail of the coefficients of the terms involving the remainders from the various applications of the Division Theorem.

Note that $a \divides b \implies \gcd \set {a, b} = a$, from GCD of Integer and Divisor.