3
$\begingroup$

Given $n$ pairwise coprime natural numbers $m_{1}, \dots, m_{n}$ with remainders $y_{i}$, for all $i \leq n$. Furthermore, we have a target interval $I := \left[ a, b \right]$, with $1 \leq a < b \leq M$, $M := \prod_{i = 1}^{n} m_{i}$.

The task is, to find all tuples $T := \left(y_{1}, \dots, y_{n}\right)$ such that

$$ \exists \ x \in I, \forall i \in [1:n], x \equiv y_{i} \mod m_{i}. $$

  1. Does exist a way to find all $T$'s apart from trivial cases like $I = [1, M]$ or brute forcing?
  2. Or as even harder task: Does exist a way to find all $T$'s if you limit the set of allowed remainders? (Like, in our example for $m_{2} = 5$, for example only allow the remainders $y_{2}$ to be $\{ 1, 3 \}$.)

Edit:
Since the problem seems to be not clear for everybody, I want to give an example.

Be $m_{1} = 3$, and $m_{2} = 5$, so we have possible remainders $y_{1} \in \{ 0, 1, 2 \}$, and $y_{2} \in \{ 0, 1, 2, 3, 4 \}$.

It follows the two equations

$$ x = 3k_{1} + y_{1}\\ x = 5k_{2} + y_{2}, $$

with $k_{1}, k_{2} \in \mathbb{N}_{0}$. Assuming now, we only want $x$ in the interval $I := \left[ 8, 10\right]$.

This $x \in I$ can be written as

$$ x = 8 = 3\cdot 2 + 2 = 5\cdot 1 + 3\\ x = 9 = 3\cdot 3 + 0 = 5\cdot 1 + 4\\ x = 10 = 3\cdot 3 + 1 = 5\cdot 2 + 0 $$

So, we get the tuples $T_{1} = \left(2, 3\right)$, $T_{2} = \left(0, 4\right)$ and $T_{3} = \left(1, 0\right)$.

Improve this question
$\endgroup$
19
  • 2
    $\begingroup$ The question is not clear. Do you want to determine the image of $I$ by the map $x \mapsto (x \mod m_1,\ldots,x \mod m_n)$? $\endgroup$
    – Christophe Leuridan
    Commented Oct 26, 2023 at 11:47
  • 2
    $\begingroup$ With your first sentence of "Given $n$ natural numbers $m_{1}, \dots, m_{n}$ with remainders $y_{i}$, for all $i \leq n$", the "remainders $y_{i}$" are after division by what value(s)? $\endgroup$
    – John Omielan
    Commented Oct 26, 2023 at 12:35
  • 4
    $\begingroup$ There must be several typos which need correcting for this to make sense. The double-subscripted $y_{i,j}$ aren't used outside of the first definition of $T_j$; $x$ is unbound (should it be bound by the existential quantifier?); and "find all $T_j$ such that ... there exists $T_j$" only makes sense if there's aliasing and the two references to $T_j$ are to different objects, but in that case neither of them is used anywhere. $\endgroup$
    – Peter Taylor
    Commented Oct 26, 2023 at 15:42
  • 2
    $\begingroup$ What does the first sentence mean? Does it mean that $m_j \equiv y_i \pmod{i}$ for all i,j? $\endgroup$
    – Daniel McLaury
    Commented Oct 26, 2023 at 16:20
  • 3
    $\begingroup$ @ChristopheLeuridan, re, thank you for attempting to make things clearer; but, for ambiguous questions, it is usually better, for the asker and for the community, to let the asker take the time to communicate themselves clearly, rather than for the community to edit towards a guess (inevitably with some chance of misunderstanding, because of the ambiguous phrasing) of what was meant. $\endgroup$
    – LSpice
    Commented Oct 26, 2023 at 19:35

1 Answer 1

Reset to default
0
$\begingroup$

For the first question, the number of tuples you want to find is the size of the interval, so you can't do better than finding the representation of the first number and then repeatedly incrementing it.

For the second question, generally it seems quite hard (see this, this and this question). If the sets are continuous ranges (or composed from a small number of them), and $n$ is small you can formulate this as an ILP with a small number of variables and try to solve it.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .