Suppose $A$ is a $m \times n$ - matrix with integer entries and $b$ a column vector with integer entries. Is it true, that $Ax = b$ has an integral solution, if $Ax = b$ (mod $m$) is solvable for all natural numbers $m$? How can it be proven?
The other direction of the claim is clear : If $Ax = b$ has an integral solution, then $Ax = b$ (mod $m$) is solvable for all $m$ (simply take the coefficients of $x$ modulo $m$). For one equation, the claim is also clear : $x_1a_1 + ... + x_na_n = b$ with integers $a_1,...a_n,b$ has an integral solution if and only if $gcd(a_1,...,a_n)|b$. So, if the equation is not solvable, there is no solution modulo $m:=gcd(a_1,...,a_n)$ (If $m = 1$, the equation always has a solution).
But I have no idea how to generalize this for equation systems.
The problem is only interesting, if $Ax = b$ has infinitely many solutions in the rationals, which can be quickly checked. If the kernel of $A$ has dimension 1, the problem is also quite simple.
I tried the following : Assume , the general solution of $Ax = b$ is
$\frac{x}{m} + c_1k_1 + ... +c_nk_n$ , where $x,k_1,...,k_n$ are integral vectors and $m > 1$
Then, if we can find $d_1,...d_n$ with $x+ d_1k_1 +...+ d_nk_n = 0\ (mod\ m)$ we can build an integral solution with $c_i:=\frac{d_i}{m}$ , i=1,...,n. Is this sufficient condition also necessary ? If yes, then there would at least be a brute-force-method working modulo m.
Finally, is checking the integer-solvability of $Ax = b$ NP-hard ?