Given A ∈ ℤm×n and b ∈ ℤm, we consider the issue of existence of a solution x ∈ ℕn to the system of linear equations Ax=b. We provide a discrete analogue of the celebrated Farkas lemma for linear systems in ℝn and prove that checking existence of integral solutions reduces to solving an explicit linear programming problem of fixed dimension, known in advance.
