Example

The following questions concern linear combinations of three values:

  1. Find a solution in integers to $6x + 15y + 20z = 1$.
  2. Under what conditions are their integers $x,y,$ and $z$ where $ax + by + cz = 1$? Describe a method to find such a solution, when it exists.
  3. Use your method from (b) to find a solution in integers to $15x+341y+385z=1$

  1. Note that $6x + 15y$ must always be a multiple of $\gcd (6,15) = 3$. As such, we first solve $3k+20z=1$. By inspection, $3 \cdot 7 + 20 \cdot (-1) = 1$. So we can characterize all solutions by $k=7+20n$ and $z=-1-3n$.

    Now solving $6x+15y=3$, we find $x = 3 + 5m$ and $y = -1 - 2m$.

    This means that for $6x+15y=3w$, we have $x=3w + 5mw$ and $y=-w -2mw$ as solutions.

    By our first calculation, we need $w=7 + 20n$. Substituting this into our forms for $x$ and $y$, we find:

    $$\begin{align} x&=21 + 60n + 35m + 100mn\\ y&=-7 - 20n -14m - 40mn\\ z&=-1-3n \end{align}$$
  2. We need $\gcd(a,b,c)=1$ in order to have a solution. As suggested in part (a), to find a solution, we can first find a solution to $ax+by=\gcd(a,b)$; then find a solution to $\gcd(a,b)\cdot k + cz = 1$; and finally, multiply the first solutions for $x$ and $y$ by the solution for $k$.

  3. $x = 298, y=-149, z=12$ is a solution.