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 (a1, b1)…(an, bn), can we find an integer x such that x ai mod bi?
(G&J also add the rule that ai ≤ bi 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 Ci = (zai∨zbi∨zci). For each ai find pai, the aith prime number, and find pbi and pci similarly. Define ai‘ to be 0 if zai is a positive literal, and 1 if it’s a negative literal, and define bi‘ and ci‘ similarly. Now for each clause, use the regular Chinese Remainder theorem to find a value xi where:
- xi ai‘ mod pai
- xi bi‘ mod pbi
- xi ci‘ mod pci
Our system of incongruences will be:
- x 2 (mod 3)
- x 2,3 (mod 5)
- x 2,3,4,…pt (mod pi) (pt is the tth prime number)
The above incongruences are there to force x to be 0 or 1 mod each pi. I think these correspond to true-false values to the variables in the SAT instance (x being 0 mod pi means setting that variable false, making it 1 mod pi means setting that variable true)
- x xi (mod pai*pbi*pci) for each i
This turns out to be O(n+t3) 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 ai‘ (and b and c), this means that the variables can’t be set to be equal to all of ai‘, bi‘ and ci‘. Because of how our xi was chosen, this means that x is not congruent to xi (mod pai*pbi*pci).
Difficulty: 7. This is a cool short reduction, but the way the x value works is something you don’t usually see.