Transforming 3 SAT to Simultaneous In-Congruence Problem?
Given a SAT instance on $n$ variables, find $n$ relatively prime integers $p_1,\ldots,p_n \geq 2$ of polynomial size (for example the first $n$ primes). The idea is to encode the value of variable $x_i$ as $x \bmod{p_i}$. The first step is to ensure that the variables are indeed binary. To this end, for each $i$ and for each $2 \leq a &lt; p_i$, we add the constraint $x \not\equiv a \pmod{p_i}$.

Each clause involving $p_i,p_j,p_k$ corresponds to one forbidden value of $x \bmod{p_ip_jp_k}$ via the Chinese reminder theorem. For example, consider the clause $x_i \lor x_j \lor \lnot x_k$. Find the value $0 \leq a &lt; p_ip_jp_k$ which satisfies $a \equiv 0 \pmod{p_i}$, $a \equiv 0 \pmod{p_j}$, and $a \equiv 1 \pmod{p_k}$. Add the constraint $x \not\equiv a \pmod{p_ip_jp_k}$.

The resulting system is completely equivalent to the original 3SAT instance.