# Solving system of equations using Chinese remainder theorem

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?

• 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$. Dec 13, 2020 at 21:47 • Thank you. I tried to update it now. – HaBo Dec 13, 2020 at 21:50 • Is it the same$a_1$and$b_1$for each equation? Dec 13, 2020 at 21:54 • No, sorry. I messed it up when I edited it. – HaBo Dec 13, 2020 at 21:59 • Your system of equations is the same as solving$x\equiv -a_i \pmod{b_i}\$. Dec 14, 2020 at 0:55

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