Back to the problems we’ve skipped over, starting with a cool take on the classic “Chinese Remainder Theorem”.

**The problem: **Simultaneous Incongruences. This is problem AN2 in the appendix.

**The description: **Given n pairs of positive integers (a_{1}, b_{1})…(a_{n}, b_{n}), can we find an integer x such that x a_{i} mod b_{i}?

(G&J also add the rule that a_{i} ≤ b_{i} for all i, but we can easily make that happen by doing division)

**Example: **I think it’s easier to see this as the actual congruences:

Can we find an x such that:

- x 1 mod 2
- x 2 mod 3, and
- x 3 mod 4?

If we chose x as 4, we’ll see that it works. For a simple example of a case that fails, we can do:

- x 1 mod 3
- x 2 mod 3, and
- x 3 mod 3

**Reduction: **I found this reduction in the Algorithmic Number Theory book by Bach and Shallit. Their Theorem 5.5.7 calls this the “Anti-Chinese Remainder theorem”. They reduce from 3SAT.

Our formula will have t variables and each clause in our formula is made up of 3 literals, which we’ll represent as C_{i} = (z_{ai}∨z_{bi}∨z_{ci}). For each a_{i} find p_{ai}, the a_{i}th prime number, and find p_{bi} and p_{ci} similarly. Define a_{i}‘ to be 0 if z_{ai} is a positive literal, and 1 if it’s a negative literal, and define b_{i}‘ and c_{i}‘ similarly. Now for each clause, use the regular Chinese Remainder theorem to find a value x_{i} where:

- x
_{i}a_{i}‘ mod p_{ai} - x
_{i}b_{i}‘ mod p_{bi} - x
_{i}c_{i}‘ mod p_{ci}

Our system of incongruences will be:

- x 2 (mod 3)
- x 2,3 (mod 5)
- …
- x 2,3,4,…p
_{t}(mod p_{i}) (p_{t}is the t^{th}prime number)

The above incongruences are there to force x to be 0 or 1 mod each p_{i}. I *think* these correspond to true-false values to the variables in the SAT instance (x being 0 mod p_{i} means setting that variable false, making it 1 mod p_{i} means setting that variable true)

- x x
_{i}(mod p_{ai}*p_{bi}*p_{ci}) for each i

This turns out to be O(n+t^{3}) incongruences by the Prime Number Theorem.

Each clause in the SAT instance is satisfiable unless all 3 literals are false. By the way we’ve created our a_{i}‘ (and b and c), this means that the variables can’t be set to be equal to all of a_{i}‘, b_{i}‘ and c_{i}‘. Because of how our x_{i} was chosen, this means that x is not congruent to x_{i} (mod p_{ai}*p_{bi}*p_{ci}).

**Difficulty: **7. This is a cool short reduction, but the way the x value works is something you don’t usually see.