Sorry for missing last week- my grading backlog is getting out of hand.

**The problem: **Simultaneous Divisibility of Linear Polynomials. This is problem AN3 in the appendix.

**The description: **Given two sets A and B, each containing n vectors, each vector having m+1 integer entries (so for example, vector a_{i} has values a_{i}[0] through a_{i}[m]) , can we find m positive integers x_{1} through x_{m} such that for each pair of vectors a_{i} and b_{i},

(a_{i}[0] + a_{i}[1]*x_{1} + a_{i}[2]*x_{2}+…+a_{i}[m]*x_{m}) divides (b_{i}[0] + b_{i}[1]*x_{1} + b_{i}[2]*x_{2}+…+b_{i}[m]*x_{m})

**Example: **Suppose a_{1} was (1,2,3), b_{1} was (2,4,6), a_{2} was (4,2,4), and b_{2} was (7,9,10). Then if I pick x_{1} = 3, x_{2 }= 2, a_{1}‘s equation evaluates to 13 and b_{1}‘s evaluates to 26. a_{2}‘s equation evaluates to 18, and b_{2}‘s equation evaluates to 54. Since both a values divide their corresponding b values, we have found an x_{1} and x_{2} that work.

**Reduction: **The paper I found by Lipschitz that has the reduction reduces from Quadratic Congruences. He starts by assuming that m ≤ 2n because at most 2n of the a_{i} and b_{i} are independent (and so the extra variables can be made equivalent to the first 2n variables by transformation). He also uses a variation of Quadratic Congruences that states the problem is still NP-Complete if c ≤ b/2. Then given a,b, and c, we build our divisibility problem with 5 formulas over the variables x, y, u, and v:

- x+u | c+1
- 4y + v | b
^{2}-1
- x+b | y-b
^{2}
- x+b+1 | y-(b+1)
^{2}
- b | y-a

It turns out that if we can find an x such that x^{2} ≡ a mod b if and only if we can find x,y,u, and v to satisfy those divisibility problems.

If we can solve the quadratic congruence, then setting y=x^{2}, u = c-x+1 and v = b^{2} – 4x^{2} + 1 satisfies all of the divisibility equations.

In the other direction, if we have found x,y,u, and v that works, we know:

- x ≤ c (which is ≤ b/2) from the first equation
- y ≤ b
^{2}/4 from the second equation
- y = x
^{2} + k(x+b)*(x+b+1) for some k ≥ 0 from the 3rd and 4th equations

Suppose k is not 0, and thus y is not equal to x^{2}. Then y has to be > b^{2}, which violates the second fact above. So k is really 0 and y=x^{2}. Then the last equation is a restatement of the quadratic congruence problem, and y (=x^{2} ) is congruent to a mod b.

**Difficulty: **7. I think the way this all works out is very slick, and I like how the equations give you the answer, but I have no idea how you’d come up with these equations on your own.