When is the equation $Ax = b$ solvable in the integers?

Question

Let $A$ be an $m\times n$ matrix with integer entries, $b$ a column-vector with $m$ integer entries.

Suppose the equation $Ax = b$ has infinitely many solutions.

It is clear that the general solution of the equation $Ax = 0$ can be written as a linear combination of vectors with integer values.

But what about a special solution of $Ax = b$ ?

When does a vector $x$ with $n$ integer entries exist with $Ax = b$? In other words, when is $Ax = b$ solveable in the integers ? If it is, how can I find the integer solution ?

I tried to implement the function linsolve in PARI/GP. PARI/GP deliveres the kernel of A with integral entries. Using matsupplement, I can find a special solution, if no column-exchanges are required. But for the martrix

$$\begin{pmatrix} 1 & 1 &3 \\ 0 & 0 &1 \\ 0 &0 &0 \end{pmatrix}$$ and the column vector $\begin{pmatrix}8 \\ 1 \\0\end{pmatrix}$ , the wrong solution $\begin{pmatrix}5 \\ 1 \\0\end{pmatrix}$ is given instead of the correct $\begin{pmatrix}5 \\ 0 \\1\end{pmatrix}$. Is there a way to always find a correct special solution with PARI/GP, assuming the system is solveable ?

Answer 1

In the special case that your integer matrix $A$ is total unimodular it seems you can use the standard simplex algorithm.

See here: Using total unimodularity.

Answer 2

The Hermite normal form was introduced to solve this very problem. It transforms the system $Ax=b$ into another one $Hy=b$ where the columns of $H$ are in echelon form. It is easy to solve the latter system, and one just looks whether the solution $y$ has integral entries. In Pari/GP the function is mathnf.