1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Checkout the multivariable chinese remainder theorem. $\endgroup$ – Willem Hagemann Jun 17 at 16:26
  • $\begingroup$ Thanks Willem for the pointer. I did come across the multivariable chinese remainder thm, but my understanding is that this is for solving a system of linear modular equations. Do you have a specific reference you could share that applies to my specific case? Thanks. $\endgroup$ – geguze Jun 17 at 16:38
2
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ absolutely right, i did not specify what 'smallest' means. Yes, I was thinking about $\sum_i t_i$ as cost function, thanks for highlighting this, and yes, they result for this is indeed $(0,0,3,0)$. While I am interested about the numerical solution, I am even more interested about a theorem that describes the solution for these types of equations. Do you know of any reference? I am, implicitly, assuming this is a well studied problem in modular arithmetic, but I am a complete outside on this, so I might be completely wrong. $\endgroup$ – geguze Jun 17 at 18:37
  • $\begingroup$ Being more careful about the statement I made before. The overall goal is to minimize $\sum_i x_i$ which then boils down to some linear integer program in the $t_i$'s variables. $\endgroup$ – geguze Jun 17 at 19:09
  • $\begingroup$ Sorry, I just realized I gave you $x$ values but made it sound like $t$ values. Assuming your objective, whatever it is, is in terms of the $x$ variables, you do not need the $t$ variables at all. I know nothing about Diophantine equation results, so I can't comment on whether there are any relevant theorems. $\endgroup$ – prubin Jun 18 at 22:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.