Given coprime moduli $m_1,\ldots,m_n$ with $k\ge2$ residues in each modulus, what is the least nonnegative value congruent to one of the specified residues to each modulus?
Obviously it must be less than $M=m_1m_2\cdots m_n$, but it seems like it should be closer to $k^{-n}M.$ Can anything along these lines be proved, perhaps with additional assumptions on the residue classes or moduli?
I'm interested in problems where storing $k^n$ residues would be memory-prohibitive and looping through each of the $k^n$ solutions would be too time-consuming. I'm hoping for some nice asymptotic result but an algorithm for computing this efficiently would be welcome as well. (The assumption that the number of residue classes for each modulus is fixed is not essential; the generalization with $k_i\ge2$ residue classes to modulus $m_i$ would be interesting as well.)
Example: Find a number which is {0, 1} mod 3, {2, 4} mod 5, and {1, 3} mod 7. Clearly you can find a number smaller than 105 by taking any residue class for each modulus and CRTing them together. The possible residue classes are {22, 24, 52, 57, 64, 87, 94, 99} mod 105, so 22 is the least value.