Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
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

1 Answer 1

up vote 1 down vote accepted

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.

In general, a solution may be found using the method of successive substitution.

share|improve this answer
    
I like this approach, the notation is definitely more appropriate. –  Gareth A. Lloyd Jan 19 '12 at 10:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.