0
$\begingroup$

How can I generate for a given solution of a linear diophantine equation all solutions?

For example let $21x+12y+9z=9$. I found one solution to be $(-3+3t,6-6t,t),t\in\mathbb Z$. How can I generate more solutions, or how can one be sure to have found all solutions?

I am even more interested in the general case for a linear diophantine equation with $n$ variables, i.e. $a_1x_1+\dots a_nx_n=c$. Suppose I have found one solution $(x_1,\dots x_n)$, how I can find all solutions for this equation?

Addendum: I am familiar with the case $n=2$.

$\endgroup$
  • 1
    $\begingroup$ As usual, general solution is the sum of the one solution and the general solution to the homogeneous equation $a_1x_1+\dots a_nx_n=0$. But this is not particularly useful for large $n$. For a general solution algorithm see e.g. Bernstein's paper. $\endgroup$ – Conifold May 2 at 9:55
0
$\begingroup$

Note: if $(x,y,z)$ is a solution in this case, $(x+1,y-1,z-1)$ is also a solution as: $$21=12+9$$ This allows you to find $(4,-7,1)$ and get: $$(5,-8,0)\\(6,-9,-1)\\\vdots$$ Noting $4(21)-7(12)=0$ we can also change signs to get $(-4,7,1)$ which gives:$$(-3,6,0)\\(-2,5,-1)\\\vdots$$ In some cases, it's as simple as noting a relation among coefficients. As to knowing you've found them all, that likely takes conditions of solution not producing another in a given way.

$\endgroup$

Your Answer

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