2
$\begingroup$

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.

  • 0
    \exists \delta : a+\delta \pmod{c} \le n+\delta \pmod{c} < b+a+\delta \pmod{c} 2012-01-16

1 Answers 1

2

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.

  • 0
    I like this approach, the notation is definitely more appropriate.2012-01-19