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

Let $f$ and $g$ be primitive polynomials over $\mathbb{Z}$. Decide if the following is true:

$f(x) \mid g(x)$ for infinitely many $x\in\mathbb Z$ implies $f\mid g$ as polynomials in $\mathbb{Z}[x]$.

Two comments:

  • for $f = 2$ and $g = x+1$, we have $f\nmid g$, but $f(x) \mid g(x)$ for infinitely many $x\in\mathbb{Z}$. For that reason, I've added the requirement "primitive". I hope that I didn't miss any further trivial condition one should impose on $f$ and $g$.

  • If we replace divisibility by equality, $f(x) = g(x)$ for sufficiently many $x\in\mathbb Z$ implies $f = g$. Namely, it suffices to have $f(x) = g(x)$ for at least $\max(\operatorname{deg}(f),\operatorname{deg}(g))$ values $x\in\mathbb{Z}$. However, for $f = x$ and $g$ a polynomial with constant coefficient $a\neq 0$, we have that $f(d) \mid g(d)$ for all divisors of $a$, but $f\nmid g$ (see the comment of André Nicolas). So no finite bound on the number of $x\in\mathbb Z$ with $f(x) = g(x)$ depending only on $\deg(f)$ and $\deg(g)$ will imply $f \mid g$.

share|cite|improve this question
Minor point, in your example for the first comment, if $f(1) =0$ and $g(1) \neq 0$, then you know that $f \not \mid g$. – copper.hat Sep 19 '13 at 16:48
This is essentially repeating your example. No pure degree bound can work, for if $f(x)=x$ and $g(x)$ has non-zero constant term divisible by many integers, then $f(a)$ divides $g(a)$ for many $a$, but $f$ does not divide $g$. – André Nicolas Sep 19 '13 at 17:14
@copper.hat: True. But what's the point on my question? It's clear that $f(x)\nmid g(x)$ for a single value of $x$ implies $f\nmid g$. But my question is about conditions on sets $S\subseteq\mathbb Z$ with $f(x)\mid g(x)$ for all $x\in S$ implying $f\mid g$. – azimut Sep 20 '13 at 0:13
@AndréNicolas: Thank you, good point. So we should go for infinite $S$, I guess. I've updated my question. – azimut Sep 20 '13 at 6:31
up vote 2 down vote accepted

Write the rational fraction $g(x)/f(x)$ as $q(x) + r(x)$ where $q \in \Bbb Q[X]$ and $r \in \Bbb Q(x)$ with $r(\infty) = 0$. Let $d$ be the least common denominator for the coefficients in $q$. Then for $x \in \Bbb Z$, $q(x) \in \frac 1d \Bbb Z$. When $|x|$ is large enough, we can make $|r(x)| < 1/d$, and so $g(x)/f(x)$ can only be an integer if $r(x)=0$ and $q(x)$ itself is that integer.

If $g(x)/f(x)$ is an integer for infinately many integers $x$, this implies that $r(x)=0$ for infinitely many integers, and so $r = 0$, and $f(x) = q(x)g(x)$.

Multiplying this by $d$ we obtain $df = (dq)g$ where $dq$ and $g$ are primitive polynomials over the integers. Hence by Gauss' lemma, $df$ is also primitive, which shows that $d=1$, and $f=qg$ with $q \in \Bbb Z[X]$

share|cite|improve this answer
Great answer. Didn't think about looking at $f/g$ as a rational function. Thanks! – azimut Sep 20 '13 at 13:05
@azimut : well it's really the same as the euclidean division of $g$ by $f$ : $q$ is the quotient and $rf$ is the rest. This way makes it clearer what to do with them. – mercio Sep 20 '13 at 14:29

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.