Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
@Brian Thanks for editing. – Reader Dec 2 '12 at 13:33
up vote 1 down vote accepted

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.

share|cite|improve this answer
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.


@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.

share|cite|improve this answer
Thanks for your answer. – Reader Dec 2 '12 at 13:33
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
hardmath: I'll insert this into the answer I gave. Thanks. – coffeemath Dec 2 '12 at 14:39

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.