Minimal positive solution of linear congruence equations in multiple variables I am definitely new when it comes to equations over integers so I am not even sure the nomenclature (modular linear congruence equation) is correct.
I am interested to solve equations over the integers such as:
$$
   a_1 x_1 + a_2 x_2 + \dots + a_n x_n = b\pmod c,
$$
with $a_i, x_i \in \mathbb{Z}$. Because of the modular arithmetic we have actually $n+1$ unknowns by writing:
$$
   a_1 x_1 + a_2 x_2 + \dots + a_n x_n + k c = b,
$$
for $k\in \mathbb{Z}$.
I found one can find parametric solutions but among those I am interested to minimal positive solutions.
One can imagine, potentially, to set up an optimization problem (of course the integer requirements can make the problem complicated) to achieve that, but I was trying to understand if there are (better) established methods that can tackle this problem.
To make this last statement more concrete, consider the following example:
$$
 x_1 + 2 x_2 + 3 x_3 = 9 \pmod{10}
$$
The the solution sets can be written as (I used SymPy to solve it):
\begin{align}
   x_1 &= t_0\\
   x_2 &= t_0 + t_1\\
   x_3 &= 19 t_0 + 16 t_1 + 10 t_2 - 27\\
   x_4 &=  -6 t_0 - 5 t_1 - 3 t_2 + 9
\end{align}
for some $t_0,t_1,t_2\in \mathbb{Z}$. I am interested to find the smallest $t_0$, $t_1$ and $t_2$ such that $x_i \geq 0$ for $i\in \{1,\dots,4\}$.
I could set up an integer linear program that attempts to find a solution. I am curious to know if: (1) is this the right way to approach the problem? (2) if not, is there a better way to look at such a problem? (3) any relevant literature that anyone could point me to that is useful in this context.
 A: Yes, an integer program is a reasonable way to solve this, assuming that (a) your actual equation or system of equations (if you are thinking of having multiple equations) does not become overly large and (b) if you are content with a numerical solution (as opposed to a theorem describing the solution, or a simple algorithm anyone can apply by hand).
From your problem statement, it is a bit unclear what your criterion "smallest $t_0$ ..." would be. Possibilities (which could produce different results) include "smallest $t_0$", "smallest $t_1$", ..., smallest $\sum_i t_i$, or smallest $\max_i t_i$. FYI, for your example, the sum is minimized by (0, 0, 3, 0) (which also minimizes three of the four variables). (0, 248, 1, 49) and (9, 0, 0, 0) are also solutions (the first tied for minimizing $t_1$, the second tied for minimizing all other variables). (2, 2, 1, 0) minimizes the largest value of any variable (2).
Correction: The above results are for the $x_i$ variables, not the $t_i$. For instance, $x=(2, 2, 1, 0)$ minimizes $\max \lbrace x_1, x_2, x_3 \rbrace$.
