General Chinese Remainder Theorem for sets

Question

Instead of a normal system of congruences I have something like this: $$ \lbrace x \in S_i \bmod m_i \rbrace_{i = 1,...,t}$$

where $m_i$ are integers and $S_i$ are sets of integers for all $i = 1,...,t$. Now I'm interested in finding all solutions of this system. The moduli may not be pairwise coprime so this is good to know.

For example we have the following system:

• $ x \in \lbrace 15, 16, 17, ..., 45 \rbrace \bmod 60 $
• $ x \in \lbrace 10, 11, 12, ..., 30 \rbrace \bmod 40 $
• $ x \in \lbrace 6, 7, 8, ..., 18 \rbrace \bmod 24 $

In this case we would get $$ x \in \lbrace 15, 16, 17, 18, 30, 90, 102, 103, 104, 105 \rbrace \bmod 120 = \text{lcm} \left( 60, 40, 24 \right)$$

as the solution.

Do you know an algorithm that can compute the solutions or a paper etc. that may help me? I haven't seen anything about CRT with sets, only about the case with non pairwise-coprime modulis or the CRT for general rings. So even a hint could possibly help me a lot!

Thanks :)

Answer 1

First, note that for suitable integers $a,x,n,k$ $$x\equiv a\pmod n\iff x\equiv a+jn\pmod{kn}\text{ for some }0\le j\le k-1$$

To solve the system, begin computing $M=\text{lcm}(m_1,\ldots,m_t)$.

Then apply the former to each set writing the congruences mod $M$. For example: $$x\in\{15,16,\ldots,45\}\pmod{60}\iff x\in\{15,16,\ldots,45,75,76,\ldots,105\}\pmod{120}$$

To finish, you simply compute the intersection of the sets.

Answer 2

$$x \in \{ 15, 16, 17,\ldots, 45 \} \bmod 60 \implies\\ x\notin\{0,\pm1,\pm2,\pm3,\ldots,\pm14\}\bmod 60 \\ x \in \{ 10, 11, 12,\ldots, 30 \} \bmod 40 \implies \\x\notin\{0,\pm1,\pm2,\pm3,\ldots,\pm9\}\bmod 40 \\ x \in \{ 6,7,8, \ldots, 18 \} \bmod 24 \implies \\ x\notin\{0,\pm1,\pm2,\pm3,\ldots,\pm5\}\bmod 24$$

first 2 show us that since lcm(60,40)=120 and 14+9>20 that all number in between two multiples of 40 are out as well as 9 to either side. with 14>9 and 120 a multiple of both 40 and 60 so are all numbers more that 105 and less than 15 mod 120.

19 to 29 , and 91 to 101 are knocked out by mod 24 ( which still fits under lcm 120). you then get your answer.

It will depend on regular patterns in your sets to have an easy time with this though.