# Relationship between divisibility of polynomials and divisibility of its evaluations

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]$.

• 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$.

-
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

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]$
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