Saturday, 14 June 2014

elementary number theory - How do you generate for a given solution for a linear diophantine equation more solutions




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


Answer



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.


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...