# How do I solve a linear Diophantine equation with three unknowns?

Find one integer solution to the Diophantine equation
\begin{equation*}
18x+14y+63z=5.
\end{equation*}

If this were only a linear equation over $\mathbb{Z}^2$, then I could easily solve it by using the extended Euclidean algorithm… but I have no idea how to do this with more than 2 unknowns…

#### Solutions Collecting From Web of "How do I solve a linear Diophantine equation with three unknowns?"

You solve $18 u + 14 v = 2 = \gcd(18,14).$ Solve $2 w + 63 z = 1.$ Combine to get $18 x + 14 y + 63 z = 1.$ Then multiply all by $5.$

[For the following paragraphs, please refer to the figure at the end of the last paragraph (the figure is also available in PDF).]

The manipulations performed from steps (0) to (17) were designed to create the linear system of equations (0a), (5a), (11a) and (17a). The manipulations end when the absolute value of a coefficient of the latest equation added is 1 (see (17)).

Equation (0a) is given. It is possible to infer equations (5a), (11a) and (17a) from (0), (5) and (11) respectively without performing manipulations (0) to (17) directly. In every case, select the smallest absolute value coefficient, generate the next equation by replacing every coefficient with the remainder of the coefficient divided by the selected coefficient (smallest absolute value coefficient) – do the same with the right-hand constant – and add the new variable whose coefficient is the smallest absolute value coefficient. If the new equation has a greatest common divisor greater than one, divide the equation by the greatest common divisor (it may be necessary to divide this greatest common divisor from previous equations). Stop when the absolute value of a coefficient of the latest equation added is 1.
Then proceed to solve the linear systems of equations.

Hint $\ \color{#c00}{18\!-\!14}\,\mid\, 63\!+\!1$ $\, \Rightarrow\,16\,(18\!-\! 14)-63 = 1.\,$ Scale that by $\,5\,$ to finish.

Remark $\$ The idea is simply to search for a “small” linear combination $\,n = \color{#c00}{ia+jb}\,$ of two elements $\,a,b\,$ of $\,\{14,18,63\}\,$ such that the 3rd element satisfies $\ c\equiv \pm1 \pmod n,\,$ hence $\, \pm1 = c+kn = c + ki\,a + kj\,b\,$ thus scaling by $\pm n\,$ yields $n$ as a linear combination of $a,b,c.\,$ Above the first “small” number we see $\, n = \color{#c00}{18\!-\!14} = 4\,$ works since $63\equiv -1\pmod {\!4}.$

The reason for choosing $n$ “small” is that this increases the probability that $\,c\equiv \pm1\pmod{\! n},\,$ e.g. $100\%$ chance if $n = 2,\,$ $67\%$ if $n = 3.\,$ We know (by Bezout) that the smallest such $n$ is $\,\gcd(a,b)\,$ but – as we saw above – often simpler choices work such as $\,b-a.$

More algorithmically, we can use the Extended Euclidean Algorithm to compute $\rm\,gcd(63,18,14) = 1\,$ in a couple steps

$$\begin{array}{rrr} [1]&\ 63& 1& 0& 0\\ [2]&\ 18& 0& 1& 0\\ [3]&\ 14& 0& 0& 1\\ [2] -[3]\, =\, [4]& 4& \!\!0& 1& -1\\ 16[4] -[1]\, =\,[5]& 1& -1& 16& \!\!\!\!-16 \end{array}\qquad\qquad\qquad\quad$$

where the row $\ n\,\ a\,\ b\,\ c\,\ d\$ denotes that $\ n = 63a + 18 b + 14 c.\$ Thus the final row yields

$$\quad 1 = -63 +16(18) – 16(14)$$