# Solving modular inequalities/constraint solving

A few of my current programming problems boil down to solving inequalities over modular domains and possibility could benifit from knowledge of efficient maths/algorithms rather than brute force search version I currently use.

Given a problem of the following form:

$a,b,c,d,e,f,g,i,n \in \mathbb{Z}$

$a \le n < b+a \pmod{c}$

$d \le n < e+d \pmod{f}$

$g \le n < h+g \pmod{i}$

where $a,b,c,d,e,f,g,i$ are given constants, does a $n$ exist? In my case it is not important to known what $n$ is.

-
What does $\le \bmod m$ mean? $-3 \le 0 \le 2 \equiv -3 \bmod 5$. –  lhf Jan 16 '12 at 15:18
@lhf my notation/representation is almost certain to be wrong. I intend to have a modular based lower and upper bounds. eg. bounds of 3,6 over mod 7 gives 3,4,5 as solutions, whereas bounds 6,3 over mod 7 gives 6,0,1,2. –  Gareth A. Lloyd Jan 16 '12 at 16:23
$\exists \delta : a+\delta \pmod{c} \le n+\delta \pmod{c} < b+a+\delta \pmod{c}$ –  Gareth A. Lloyd Jan 16 '12 at 17:14

Suppose $n_1, n_2, \ldots, n_k$, are positive integers, $A_1, \ldots, A_k$ sets of integers. Does there exist an $x$ such that $x \equiv a \pmod{n_i}$ for some $a \in A_i$ for $i=0,\ldots,k$? This is how I would rephrase your question.
If $n_1, \ldots, n_k$ are pairwise coprime, the Chinese remainder theorem ensures that the system of congruences is solvable for any $A_i$ and gives you the explicit solution.