# Chinese Remainder Theorem for Remainder Intervals

Given $$n$$ natural numbers $$m_1,\dots,m_n$$ and $$n$$ remainder intervals $$[a_1,b_1],\dots,[a_n,b_n]$$ holding $$a_i < b_i$$ for all $$i\leq n$$ the task is to search for the smallest natural number $$x$$ that holds $$(\exists y_i\in[a_i,b_i]:x\equiv y_i\mod m_i) \quad \forall i \leq n$$ I don't want anyone to solve this for me. But maybe I'm missing some paper?

• You might consider the tag "reference-request" if you want to emphasize that you're more interested in pointers to the relevant literature than you are to mathematical commentary. – Greg Martin Aug 14 '19 at 17:52
• I suspect this is NP-hard if not NP-complete. I would also be interested in references to this problem. I am reminded of a continued fraction type algorithm for the postage stamp problem for n=2 or n=3; perhaps you can reduce the postage stamp problem to this. Gerhard "But Don't Try Mailing It" Paseman, 2019.08.14. – Gerhard Paseman Aug 14 '19 at 18:02
• See also cs.stackexchange.com/questions/94227/… which shows NP-hardness in the case of arbitrary $m_i$. It's possible that nothing is actually known in the case of (relatively) prime $m_i$. – Steven Stadnicki Aug 14 '19 at 20:27

First off, we may assume that $$m_i$$ are powers of distinct primes (otherwise we can split them into powers of primes and merge powers of the same prime).
There is an approach based on the Coppersmith method that may work in some cases, depending on the length of intervals and how small is the smallest solution as compared to $$M:=m_1m_2\cdots m_n$$. In fact, it's applicable for any given sets of residues modulo each $$m_i$$, not necessarily intervals. In your case these sets are $$A_i := \{ k\in\mathbb{Z}\mid a_i\leq k\leq b_i\}$$. For further details, see my other answer (where $$p_i:=m_i$$).