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
  • 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, 2019 at 9:55

1 Answer 1

Reset to default
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$

You must log in to answer this question.