Example

Find all solutions in integers to the following.

$$54321x + 9876y = \textrm{gcd}(54321,9876)$$
First, we must compute the greatest common divisor (gcd) of 54321 and 9876. We can use Euclid's Algorithm to do this: \begin{align*} 54321 &= 5 \cdot 9876 + 4941\\ 9876 &= 1 \cdot 4941 + 4935\\ 4941 &= 1 \cdot 4935 + 6\\ 4935 &= 822 \cdot 6 + \fbox{3} \leftarrow \textrm{gcd}\\ 6 &= 2 \cdot 3 + 0 \end{align*} Now, we write the gcd as various linear combinations, working our way backwards through Euclid's Algorithm, until we get the linear combination desired: \begin{align*} 3 &= 1 \cdot 4935 - 822 \cdot 6\\ 3 &= 1 \cdot 4935 - 822 \cdot (4941 - 1 \cdot 4935)\\ 3 &= 823 \cdot 4935 - 822 \cdot 4941\\ 3 &= 823 \cdot (9876 - 1 \cdot 4941) - 822 \cdot 4941\\ 3 &= 823 \cdot 9876 - 1645 \cdot 4941\\ 3 &= 823 \cdot 9876 - 1645 \cdot (54321 - 5 \cdot 9876)\\ 3 &= 9048 \cdot 9876 - 1645 \cdot 54321\\ \end{align*}

The last line gives us the solution we seek: $x=-1645$, $y=9048$.

Now that we have one solution, and given that the $\textrm{gcd}(54321,9876)=3$, the rest of the solutions can be characterized by the following where $k$ is an integer:

$$x = -1645 + \dfrac{9876}{3} k \quad , \quad y=9048 - \dfrac{54321}{3} k$$

Written more briefly, we have:

$$x = -1645 + 3292k \quad , \quad y=9048-18107k \quad \textrm{ with } k \in \mathbb{Z}$$