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

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?

share|cite|improve this question
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… ? – 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$.

share|cite|improve this answer

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


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

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.