2
$\begingroup$

I want to know if a given system of linear integer equations has an integer solution. I know it is the case if and only if it has a solution modulo $n$ for all integer $n$. What I do not know is when such a system admits a solution modulo a generic $n$.

For example, a single linear equation $\sum a_i X_i = b$ has got a solution modulo $n$ if and only if the greatest common divisor of its coefficients $a_i$ and n divides $b$. Can something similar be said about a system? I'd be satisfied with any answer. For instance just some link or refference to look up would be enough. Thanks.

$\endgroup$
2
  • $\begingroup$ What do you mean by "generic"? $\endgroup$
    – Qiaochu Yuan
    Commented Apr 11, 2012 at 17:47
  • $\begingroup$ I mean any $n$. Since my system will have integer solution if and only if it has a solution modulo $n$ for every integer, I'd like to have a criterion for deciding when the second condition is true. $\endgroup$
    – Garreta
    Commented Apr 11, 2012 at 19:51

1 Answer 1

Reset to default
1
$\begingroup$

You may find the paper at www.math.uwaterloo.ca/~wgilbert/Research/GilbertPathria.pdf helpful. It says, "If students can solve a system of linear equations by row reduction, we show how they can also find all the integer solutions to a system of linear Diophantine equations, using integer row reduction."

Many other references can be found by typing $$\rm linear\ diophantine\ systems$$ into your favorite search engine, although some of the result will only be available on subscription.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .