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.
Sources
- 1980: David M. Burton: Elementary Number Theory (revised ed.) ... (previous) ... (next): Chapter $2$: Divisibility Theory in the Integers: $2.3$ The Euclidean Algorithm