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?

$\begingroup$ You might consider the tag "referencerequest" if you want to emphasize that you're more interested in pointers to the relevant literature than you are to mathematical commentary. $\endgroup$– Greg MartinCommented Aug 14, 2019 at 17:52

2$\begingroup$ I suspect this is NPhard if not NPcomplete. 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. $\endgroup$– Gerhard PasemanCommented Aug 14, 2019 at 18:02

$\begingroup$ See also cs.stackexchange.com/questions/94227/… which shows NPhardness in the case of arbitrary $m_i$. It's possible that nothing is actually known in the case of (relatively) prime $m_i$. $\endgroup$– Steven StadnickiCommented Aug 14, 2019 at 20:27
1 Answer
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$).