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

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

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

Solution 3:

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