# $p(x) \mid q(x)$ for infinite values of $x$ (integer) implies $p(n) \mid q(n) \quad \forall n$ integer

I was working on: Kind of Functional Eq. in Integers

I found a sort of way...

but I need to show that:

$p(x) \mid q(x)$ for infinite values of $x$ (integer) implies $p(n) \mid q(n) \quad \forall n \in \mathbb{Z}$

I was told that it is always true, but I can show it just for polynomials. Is it a well known theorem, or is there an easy proof?

-
Without any hypothesis on $p$ and $q$, it is trivially false. –  Lierre Jun 22 '12 at 11:39
In fact I had some doubts. Does it become true with functions like math.stackexchange.com/questions/161578/… ? –  Problemsolved Jun 22 '12 at 11:42
What are you interested in exactly ? And it is false even for polynomials ($p(x) = 2$, $q(x) = x$). –  Lierre Jun 22 '12 at 11:43
I'm trying to solve that problem, and I was reasoning with some primes, when I got that proving that if for infitely many primes $p^d-1 \mid p^n-1$ iff $d \mid n$ would solve the problem –  Problemsolved Jun 22 '12 at 11:53
This is easy since $p^n-1 = (p^d - 1)\left(1+p^d+p^{2d}+\dotsb+p^{d\left(\frac nd-1\right)}\right)$. –  Lierre Jun 22 '12 at 11:58

let $n=dq+r$ then $p^n-1=p^{dq+r}-1=p^r(p^{dq}-1)+(p^r-1)$. Now $p^d-1|p^n-1$ implies $p^d-1|p^r-1$ but $r<d$ implies $p^r-1<p^d-1$. So $p^r-1=0$ i.e $r=0$. Hence $d|n$.

-

Let's formalize the question. Given a set of integers $S$, we want to know if it satisfies the property $P_S$:

If $p$ and $q$ are rational polynomials such that for all $x\in S$, $p(x)\mid q(x)$ and both quantities are integers, then $p$ and $q$ are integer-valued polynomials and $p(n)\mid q(n)$ for all $n\in\mathbb Z$.

By writing $p(x)=q(x)r(x)$, this is actually equivalent to the property $P'_S$:

If $p$ is a rational polynomial, then $p(x)$ is an integer for all $x\in S$ iff $p(n)$ is an integer for all $n\in\mathbb Z$.

Or, by multiplying by the gcd of the coefficients, equivalent to $P''_S$:

If $p\in\mathbb Z[X]$ and $m\in\mathbb Z$, $m\mid p(x)$ for all $x\in S$ iff $m\mid p(n)$ for all $n$.

Of course, this is not true for all $S$: when $S=2\mathbb Z$, $2\mid x$ for $x\in S$ but not for $x\notin S$. This is also never true when $S$ is finite. But there is hope because when $S$ contains arbitrarily many consecutive integers, it is well known that $P_S$ is true by interpolation with binomial coefficients.

So, would this be true when $S$ is the set of primes? No, because primes are never multiples of 6. So we can define $$p(n)=\binom{n-1}{5}$$ and $6\mid p(n)$ when $n\ne 0 \pmod 6$, but $p(n)=1 \pmod 6$ when $n=0 \pmod 6$, proving that it doesn't suffice to look at prime numbers to understand the behavior of $p$.

In fact, we have the following characterization:

Theorem: $P_S$ is true if and only if for all $n$, $\mathbb Z/n\mathbb Z\subseteq S \pmod n$, that is if and only if $S\cap(n\mathbb Z+a)\ne\emptyset$ for all $a,n$.

Proof:

• If $P_S$ is true, then given $a$ mod $n$, $p(x)=\binom{x-a-1}{n}$ is an integer-valued polynomial which is not a multiple of $n$ for all $x$, so there must be some $x\in S$ such that $n$ does not divide $p(x)$, and this implies that $x=a \pmod n$, so $\mathbb Z/n\mathbb Z\subseteq S \pmod n$.
• Suppose $\mathbb Z/n\mathbb Z\subseteq S \pmod n$. If $p\in\mathbb Z[X]$ and $p(x)=0 \pmod m$ for all $x\in S$, then $p(x)=0 \pmod m$ for all $x\in\mathbb Z/m\mathbb Z$ and therefore for all $x\in\mathbb Z$. So $P''_S$ is true.
-