Example

Find all solutions in integers to the following. $$12345x + 67890y = \textrm{gcd}(12345,67890)$$


First, we must compute the greatest common divisor (gcd) of 12345 and 67890. We can use Euclid's Algorithm to do this: \begin{align} 67890 &= 5 \cdot 12345 + 6165\\ 12345 &= 2 \cdot 6165 + \fbox{15} \leftarrow \textrm{gcd}\\ 6165 &= 411 \cdot 15 + 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} 15 &= 1 \cdot 12345 - 2 \cdot 6165\\ 15 &= 1 \cdot 12345 - 2 \cdot (67890 - 5 \cdot 12345)\\ 15 &= 11 \cdot 12345 - 2 \cdot 67890\\ \end{align}

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

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

$$x = 11 + \dfrac{67890}{15} k \quad, \quad y=-2 - \dfrac{12345}{15} k$$

Written more briefly, we have:

$$x = 11 + 4526k \quad , \quad y=-2-823k \quad \textrm{ with } k \in \mathbb{Z}$$