We’ll do this next one out of order because I think this order is better explained by the paper.

**The problem: **Non-Trivial Greatest Common Divisor. This is problem AN7 in the appendix.

**The description: **Given a set of m sequences of pairs of integers (so sequence A_{i} is <(a_{i}[1],b_{i}[1]) …(a_{i}[k],b_{i}[k])>), where each b element is ≥ 0. I’m pretty sure k can be different in each sequence. If we build the polynomials , for each i from 1 to m, does the greatest common divisor of those polynomials have degree greater than 0?

**Example:** I think the hardest part of this description is picturing the polynomials, so here’s a simple example showing how that works. Suppose m=2, and A_{1} was <(20,3),(4,2),(30,1)> and A_{2} was <(2,4),(8,1)>

(As an aside, I wish G&J didn’t use A for both the name of a sequence *and* lowercase a for the name of one of the entries of each pair. They’re not related.)

The polynomial corresponding to A_{1} is 20x^{3} + 4x^{2}+30x, and the polynomial corresponding to A_{2} is 2x^{4} +8x. The polynomial 2x is a divisor of both, and I think it’s the GCD. (If not, the GCD is larger, and so also has degree >0). So, this problem instance would have the answer “yes”.

**Reduction: **

This reduction is also by Plaisted, who did last week’s reduction, but is in his 1984 paper. His reduction is from 3SAT. In the paper, he gives an algorithm that turns a logical formula into a polynomial. The polynomial p that gets created has the property that p(z) = 0 if and only if z is an M-th root of unity (a solution to z^{M}=1). This leads to a way of setting the truth values of the logical formula: if ω is the root of unity, set variable P_{j} to true if =1, where q_{j} is the jth prime number. It turns out if you do that, you make the entire logical formula true.

So, for our problem, we’re handed a 3SAT instance with n variables. Let M be the product of the first n primes. The formula is satisfiable iff we can make all clauses true, which happens iff there is an Mth root of unity ω such that the polynomial on each clause is 0 (so we make a polynomial for each clause in the SAT formula). He states an “easy” identity (without proof) that the polynomial of A∧B is the gcd of the polynomials of A and B. So therefore if ω exists for all polynomials, the gcd has degree greater than 0.

**Difficulty**: 8. This is a little easier to follow because he states the properties of his polynomial up front. I’d like to see more proofs of his “easy” properties and to be honest, I’m not sure how the last step happens (how having ω exist means that the gcd has degree > 0). I also don’t know how you’d ask students to come up with these polynomials on their own.