# Existence of solution of a modular system of linear equations

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.

-
What do you mean by "generic"? –  Qiaochu Yuan Apr 11 '12 at 17:47
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. –  Garreta Apr 11 '12 at 19:51

## 1 Answer

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

-