10
$\begingroup$

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

$\endgroup$
  • $\begingroup$ how much are you sure about the "existence" of "one integer solution"????? $\endgroup$ – user87543 Oct 4 '13 at 1:44
  • $\begingroup$ See my answer (pointing to Cauchy's general solution) here: <math.stackexchange.com/questions/742684/…> $\endgroup$ – Kieren MacMillan Aug 23 '14 at 17:08
11
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Could you elaborate on the "combine" part? I get a solution to $18u+14v=2$ with $u=-3$, $v=4$. Then if I solve $2w+63z=1$, I get $w=-31$ and $z=1$. What do I combine where to get $18u+14v+63z=1$? I tried plugging in $u,v,z$ as I found them and I get $(-3)(18)+(4)(14)+63=65... $\endgroup$ – agent154 Oct 4 '13 at 1:56
  • 2
    $\begingroup$ @agent154 $$(18u+14v)w + 63z = 1$$ $\endgroup$ – Will Jagy Oct 4 '13 at 1:58
  • 1
    $\begingroup$ you have $18(-3)+14(4)=2$ and $2(-31)+63(1)=1$...from $18(-3)+14(4)=2$ you have $18(-3.(-31))+14(4.(-31))=2(-31)$.. now combine with $2(-31)+63(1)=1$.. $\endgroup$ – user87543 Oct 4 '13 at 1:58
  • $\begingroup$ OK, I did the math and it works out. Very complicated work to get used to... I suppose I just need to do it a few times to get familiar with the procedure. $\endgroup$ – agent154 Oct 4 '13 at 2:02
  • 1
    $\begingroup$ @agent154, do $10x + 12 y + 15 z = 163.$ $\endgroup$ – Will Jagy Oct 4 '13 at 2:15
1
$\begingroup$

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

enter image description here

$\endgroup$
  • $\begingroup$ The extended euclidean algorithm can be presented much more simply - see my answer and its link. $\endgroup$ – Bill Dubuque Jun 27 '17 at 15:49
  • 2
    $\begingroup$ I found several errors in my answer. However instead of replacing the answer with a correction version, I am including a link to the correction: researchgate.net/publication/…. $\endgroup$ – John Frederick Chionglo Jul 23 '17 at 9:13
1
$\begingroup$

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

See here for another worked example.

$\endgroup$
  • $\begingroup$ +1 For showing the extended euclidean algorithm approach-- a fine example. $\endgroup$ – Rustyn Jul 13 '17 at 7:42
  • $\begingroup$ @Rustyn I added a Remark that explains the idea behind the optimization employed in the Hint. $\endgroup$ – Bill Dubuque Jul 13 '17 at 14:42
  • $\begingroup$ Hey Bill, could you please help me with this question regarding the general solution of a multivariable, linear Diophantine equation? $\endgroup$ – TheSimpliFire Oct 17 '18 at 16:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.