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.

$\endgroup$
  • 3
    $\begingroup$ What does $\le \bmod m$ mean? $-3 \le 0 \le 2 \equiv -3 \bmod 5$. $\endgroup$ – lhf Jan 16 '12 at 15:18
  • $\begingroup$ @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. $\endgroup$ – Gareth A. Lloyd Jan 16 '12 at 16:23
  • $\begingroup$ $\exists \delta : a+\delta \pmod{c} \le n+\delta \pmod{c} < b+a+\delta \pmod{c} $ $\endgroup$ – Gareth A. Lloyd Jan 16 '12 at 17:14
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I like this approach, the notation is definitely more appropriate. $\endgroup$ – Gareth A. Lloyd Jan 19 '12 at 10:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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