# Polynomials with roots modulo every integer

In the paper Polynomials with roots modulo every integer, in section $2$, the authors say:

Here we assumed implicitly that the greatest common divisor of the coefficients of the polynomial $P(x) = a_nx^n + · · · + a_0$ is $1$ $–$ otherwise the factorization is non-unique.

Why is it so?

-
@Brian Thanks for editing. – Reader Dec 2 '12 at 13:33

The quoted comment from the paper is parenthetical and follows an assumption about integer polynomial $P(x)$ being a product of factors "irreducible over $\mathbb{Q}$":

$$P(x) = h_1(x) \cdot \ldots \cdot h_\nu(x)$$

The paper's authors then note their assumption that the GCD of coefficients is 1, which defines that polynomial $P(x)$ is primitive.

The presence of a nonunit common divisor of coefficients would make the product as irreducibles over $\mathbb{Q}$ "non-unique". Before describing that implication, note the authors own remark, still within the parenthetical comment, that "this has no bearing on the paper, since for our results $P$ may be replaced by" $P$ divided by the GCD of its coefficients, which would then be an equivalent (for the sake of finding roots) primitive polynomial.

Uniqueness of a factorization always has two conventional caveats: order of factors is not important (when multiplication is commutative) and the factors themselves are only unique up to multiplication by a unit (associates). Therefore moving a nonunit constant divisor from one factor to another creates a different factorization. It also is not allowed to treat the nonunit constant divisor as one of those factors "irreducible over $\mathbb{Q}$", because the constant divisor becomes a unit as a rational number.

It might have been clearer if the authors had stated that primitivity of $P(x)$ could be assumed without loss of generality (by dividing out any nonunit constant divisor), and not raising unnecessarily an issue of non-unique factorizations.

-
Thanks a lot hardmath. – Reader Dec 2 '12 at 16:07

Say the factorization was $p(x)= q(x) \cdot r(x)$. If $q(x)$ and $r(x)$ had a common factor, say $d(x)$, one could write $q(x)=d(x)a(x)$ and $r(x)=d(x)b(x)$, and then $$p(x)=q(x)r(x)=[d(x)^2]a(x)(b(x)$$ would be two different factorizations of $p(x)$, unless $d(x)$ were a unit in the set of polynomials.

EDIT:

@hardmath has pointed out that, in the paper referenced, the statement was to the effect that the polynomial $p(x)$ being factored should not have a nonunit common factor among its coefficients. This is in a way a case of the above. If one assumes that $$p(x)=q(x)r(x)...$$ is a unique factorization into irreducible polynmomials $q(x),r(x),...$ then a nonunit common factor $k$ among the coeffieints of $p(x)$ could be put with any of the factors $q(x),r(x),...$ and then one would obtain different factorizations of $p(x)$. As the author points out, this can be avoided anyway simply by working with $p(x)/d$ where $d$ is the gcd of the coefficients of the given $p(x)$.

But this is built into the statement of unique factorization in a polynomial ring $R[x]$ over a ring $R$, and in statements I've seen one has an initial unit, then a unique factorization of a ring element from $R$, then the product of various irreducible polynomials of degree one or more. As elements of $R[x]$ the irreducible ring elements of $R$ itself count as irredicuble polynomials, of degree zero.

-
At issue in this question is whether the GCD "of the coefficients of the polynomial... is 1", not whether two factors of the polynomial have a common factor. An example would be that $2x^2 - 2$ can be factored either as $(2x+2)(x-1)$ or as $(x+1)(2x-2)$. These factorizations are considered distinct because they cannot be reconciled by multiplication by a unit. This answer posits two factors of $p(x)$ which have a (nonunit) commmon factor $d(x)$. $d(x)$ is then a repeated factor of $p(x)$, but this doesn't imply the coefficients of $p(x)$ have a nonunit common factor. – hardmath Dec 2 '12 at 13:56