Garey and Jhonson mentions that a 3-SAT Problem can be transformed to another NP-Complete Problem - Simultaneous incongruences (AN2):
Given a collection $[(a_1,b_1),…,(a_n,b_n)]$ of ordered pairs of positive integers with $a_i≤b_i$ for $1≤i≤n$, is there an integer $x$ such that for all $i$, $x≢a_i(mod\ b_i)$?
But I am struggling with the transformation and not much clue how to go about it nor can find any literature on it. Thus, needed help with the transformation?
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 < 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 < 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.
