3
$\begingroup$

I have a system of equations on that I would like to solve programatically:

$(x + a_1) \bmod b_1 = 0$

$(x + a_2) \bmod b_2 = 0$

$...$

$(x + a_i) \bmod b_i = 0$

$a$ and $b$ are given, and I would like to find the smallest positive solution for $x$. The numbers are too big to iterate through all possible solutions. I think it should be possible to solve it using the Chinese remainder theorem, but I haven't been able to get from one to the other. How can I translate this problem into a problem that can be solved using the CRT?

$\endgroup$
6
  • $\begingroup$ Welcome to MSE. Please use MathJax to format your posts. To begin with, surround math expressions (including numbers) with $ signs and use _ for subscripts. $x_1$ comes out as $x_1$. $\endgroup$
    – saulspatz
    Dec 13, 2020 at 21:47
  • $\begingroup$ Thank you. I tried to update it now. $\endgroup$
    – HaBo
    Dec 13, 2020 at 21:50
  • 1
    $\begingroup$ Is it the same $a_1$ and $b_1$ for each equation? $\endgroup$
    – Bernard
    Dec 13, 2020 at 21:54
  • $\begingroup$ No, sorry. I messed it up when I edited it. $\endgroup$
    – HaBo
    Dec 13, 2020 at 21:59
  • 1
    $\begingroup$ Your system of equations is the same as solving $x\equiv -a_i \pmod{b_i}$. $\endgroup$
    – peterwhy
    Dec 14, 2020 at 0:55

1 Answer 1

1
$\begingroup$

Your system of equations is the same as solving $x\equiv -a_i \pmod{b_i}$.

$\endgroup$

You must log in to answer this question.