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

Question

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...

Answer 1

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.$

Answer 2

Hint $\ \color{#c00}{18\!-\!14}\,\mid\, 63\!+\!1 $ $\, \Rightarrow\,\overbrace{16\,(18\!-\! 14)-63 = 1}^{\textstyle 18x + 14y + 63z = 1}.\,$ Scale that by $\,5\,$ to get $\,d=5\,$ on RHS.

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 d\,$ yields $d$ as a linear combination of $a,b,c.\,$ Above the first "small" number we see is $\, n = \color{#c00}{18\!-\!14} = 4\,$ works since $63\equiv -1\pmod {\!4}.\,$ Notice that we could replace $\, k = \pm1\,$ by any divisor of $\,d,\,$ then scale by $\,d/k\,$ to get $\,d\,$ on RHS.

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.$

Below we will see that the above optimization works when the extended Euclidean algorithm terminates in a couple steps.

Algorithmically, using the Extended Euclidean Algorithm to compute $\rm\,gcd(63,18,14) = 1\,$

$$\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)$$

See here for another worked example, and see here for an explicit formula for the general trivariate linear Diophantine equation (in terms of solutions of associated bivariate equations).