Funky congruences

Question

Suppose we have the remainders: {$(a^0_1, a^1_1), \ldots, (a^0_n, a^1_n)$} and the moduli {$c_1, \ldots, c_n$}. We want to know if there exists $b_1, \ldots, b_n \in$ {0,1} and $m \in \mathbb{N}$ such that:

$$ \begin{array}{lcl} m & = & a^{b_1}_1 \quad (\mod c_1) \newline \\ & = & a^{b_2}_2 \quad (\mod c_2) \newline \\ & = & \ldots \newline \\ & = & a^{b_n}_n \quad (\mod c_n) \newline \\ \end{array} $$

That is basically a generalization of a system of linear congruences with an OR operator. Is there a nice necessary and sufficient condition for such an $m$ to exists?

Answer 1

Response to the original question. The original problem was to design a fast algorithm which decides whether the system above is solvable.

Note that the system of two congruences $x\equiv a_1\pmod{c_1}$, $x\equiv a_2\pmod{c_2}$ is solvable (and solution is unique modulo $\operatorname{lcm}(c_1,c_2)$ if and only if $a_1\equiv a_2\pmod{\gcd(c_1,c_2)}$.

At the beginning we have $n$ moduli $c_j$ and $n$ arrays $a_j=(a_j^0,a_j^1)$ of length 2, for $j=1,\dots,n$. We will also need the $2n$ by $2n$ "tiedness" matrix, which has initially all entries zero. We simply run a double loop over all pairs $i\ne j$, and on each step we do the following:

(1) Compute $c_{ij}=\gcd(c_i,c_j)$.

(2) Verify the congruences $a_i^k\equiv a_j^l\pmod{c_{ij}}$ where $a_i^k$ and $a_j^l$ run over all elements of arrays $a_i$ and $a_j$, respectively. (Note that there could be less than two elements in an array! See the next step.)

(3) If for a certain $k$ each of the congruences $a_i^k\equiv a_j^l\pmod{c_{ij}}$ is violated for all $a_j^l$, then remove $a_i^k$ from array $a_i$ and all other $a_q^p$ (from the corresponding $a_q$) which are tied to $a_i^k$ (the corresponding entry for this pair is set to be 1). Similarly, if for a certain $l$ each of the congruences $a_i^k\equiv a_j^l\pmod{c_{ij}}$ is violated for all $a_i^k$, then remove $a_j^l$ from array $a_j$ and all other $a_q^p$ (from the corresponding $a_q$) which are tied to $a_j^l$.

(4) Note that in the case of four congruences on step (3), if three are valid then the fourth one holds automatically. There are however two cases when we have only two of the four congruences $a_i^k\equiv a_j^l\pmod{c_{ij}}$ but all four elements from $a_i$ and $a_j$ are left after step (3). For these two cases we make the corresponding pairs $(a_i^k,a_j^l)$ "tied" by putting on the corresponding places in the tiedness matrix ones. The tiedness relation is further distributed along the matrix as equivalence relation, so that we put extra 1s for $a_i^k$ to reflect the tied partners of $a_j^l$, and similarly for $a_j^l$.

If at the end or at any of the steps you realize that at least one of the arrays is empty, terminate with the result "no such $m$ exists". If each of the arrays is nonempty, then the solution $m$ exists and can be obtained from the Chinese residue theorem by picking an arbitrary element from each array.

Edit. The author disappeared for a couple of days and came back with a different question. He does not need an algorithm any more but an explicit formula which says whether the system is solvable or not.

Dear Marc, this is exactly the same question(!), believe you or not. An algorithm is that explicit formula, and if there exists another one, it can be programmed and will become another algorithm. There is some heuristical evidence of why the things cannot be faster. And please make clear next time, before rewriting a question, what do you wish to get, why do you wish to get it (your motivation), and what is unsatisfactory in others' responses. This will be at least fair.

Answer 2

Here is an alternative approach, by reducing the problem to 2-SAT. It makes me ask: what if there were three values $(a_i^0, a_i^1, a_i^2)$ for each $i$ (and $b_i$'s in $\{0, 1, 2\}$)? It analogously can be reduced to some type of 2-SAT with ternary-valued variables. I don't know immediately whether either of these more general problems is NP-complete.

We need the following Theorem: Suppose we have a collection of modular constraints on $m$, of the form $\{m \equiv v_i \; (\mod{c_i})\}_{i=1\ldots n}$. Then there is no $m$ meeting all constraints iff there are two particular constraints $1 \le j < k \le n$ so that no $m$ simultaneously satisfies those two constraints.

The proof is given later below. But, assuming the theorem, we just need to determine whether $b$ exists such that all pairs of two constraints $m \equiv a_j^{b_j} \; (\mod{c_j}), m \equiv a_k^{b_k} \; (\mod{c_k})$ are pairwise satisfiable. This can be done with 2-SAT: it is easy to check which pairs of $b^j, b^k$ allow a mutual solution (see Wadim's note in his first 2 lines), then for each pair $(j, k)$ we get up to 4 constraints depending on which pairs of values for $b_j, b_k$ can hold at the same time. For example if $a_j^0 = 5, c_j^0 = 20, a_k^0 = 6, c_k^0 = 42$, we see $b_j=0, b_k=0$ cannot both hold, since $m$ would have to be both even and odd. Thus we add the clause $(b^j = 1$ OR $b^k = 1)$ to our 2-SAT instance. Repeating this gives $O(n^2)$ clauses, then we run a linear-time 2-SAT algorithm to see if $b$ exists meeting all clauses, and are done.

Proof: $\Leftarrow$ is clear, so it suffices to prove the contrapositive of $\Rightarrow$. Thus, assume we can satisfy any given two constraints; we'll constrct an $m$ that satisfies all constraints.

We focus on one prime $p$ at a time. Let $p^t$ be the maximum power of $p$ dividing any $b_i$, and let $\ell$ (which depends on $p$) be the maximizer, so $p^t | b_\ell$. The $m$ we hope to construct must satsify $m \equiv b_\ell \; (\mod{p^t})$, call this a crazy constraint. We get one crazy constraint for each prime dividing $c_1c_2\cdots c_n$. Moreover, for any $m$ that satisfies this crazy constraint, using Wadim's note twice, we deduce that $m \equiv v_i \; (\mod{\gcd(p^t, c_i)})$ for each $i$. But $\gcd(p^t, c_i)$ is just the highest power of $p$ dividing $c_i$. Thus by CRT, an $m$ which satisfies all crazy constraints (i.e. for all $p$), satisfies $m \equiv v_i \; (\mod{c_i})$, and hence all $n$ of the "input" constraints. But the crazy constraints are for relatively prime moduli, hence they all simultanouesly hold for some $m$, and we are done.