If $f \in \mathbb{Z}[x]$ is such that $p \mid f(p)$ for all primes $p$, then $x \mid f(x)$ in $\mathbb{Z}[x]$. This follows by writing $f(x) = \sum \limits_{i=0}^d c_i x^i$ and noting that $p$ divides $c_0$ for every prime $p$ implies that $c_0 = 0$.

There are perhaps several ways to generalize this to several variables; I am particularly interested in the following.

Let $f \in \mathbb{Z}[x_1,\ldots,x_n]$ be such that for every set of distinct primes $\{p_1,\ldots,p_n\}$, there exists an $i \in \{1,\ldots,n\}$ such that $p_i$ divides $f(p_1,\ldots,p_n)$. Is it true that there exists an $i \in \{1, \ldots, n\}$ such that $x_i$ divides $f(x_1,\ldots,x_n)$ in $\mathbb{Z}[x_1,\ldots,x_n]$?

I strongly believe this to be true and think there must be a nice, elementary way to show it.

  • $\begingroup$ To find a proof is not a problem, but to have it "nice and elementary" is a bit harder. Is using the fact that you have about $x/\log x$ primes up to $x$ OK? (I do not need the PNT, just Chebyshev). If so, I'll post an answer. If not, I'll have to think more. $\endgroup$
    – fedja
    Nov 19 '11 at 3:48
  • $\begingroup$ Any solution is welcome, but only "nice and elementary" will make me happy. $\endgroup$ Nov 19 '11 at 4:57
  • $\begingroup$ Also posted to math.stackexchange without any notice that it would be posted here. How rude. math.stackexchange.com/questions/83243/… $\endgroup$ Nov 19 '11 at 10:20
  • $\begingroup$ @GerryMyerson I'm still learning protocol. Thanks for linking to the previous question; wasn't trying to trick anyone. $\endgroup$ Nov 19 '11 at 13:20
  • 1
    $\begingroup$ Indeed. I guess I can shamelessly repost it on AoPS then. It seems a good olympiad type problem. $\endgroup$
    – fedja
    Nov 19 '11 at 13:23

OK, here is a sketch of one approach.

Claim 1: If $F$ is a polynomial in $n$ variables that is not identically zero, then the number of solutions to the equation $F(x_1,\dots,x_n)=0$ with prime $0<x_j<M$ is $O(\pi(M)^{n-1})$.

Proof: Induction by the number of variables with the key idea that a not identically zero polynomial of one variable can have only constant number of roots if the degree is fixed.

Claim 2: The number of distinct prime divisors of $X$ is $O(\log X)$.

Proof: Factorization.

Now assume that $f$ is not divisible by any $x_i$. Let us consider all $n$-tuples of primes $p_j\le M$. Fix $i$. Write $f=x_ig+h$ where $h$ does not depend on $x_i$. Note that $p_i|f(p_1,\dots,p_n)$ only if $p_i|h(p_1,\dots,p_n)$. Thus either $h(p_1,\dots,p_n)=0$, which gives $O(\pi(M)^{n-1})$ possible $n$-tuples $(p_1,\dots,p_n)$ by Claim 1, or $h(p_1,\dots,p_n)\ne 0$, which gives $O(\pi(M)^{n-1}\log M)$ $n$-tuples by Claim 2 (all $p_j$ with $j\ne i$ are free and once you choose them, $p_i$ must be a divisor of a number not exceeding some power of $M$).

Thus, we have at most $\pi(M)^{n-1}\log M$ $n$-tuples for which $p_i|f(p_1,\dots,p_n)$.

On the other hand, we have about $\pi(M)^n$ $n$-tuples of distinct primes. So if $\pi(M)$ is much larger than $\log M$ for infinitely many $M$, we are done. Otherwise, the primes grow as a geometric progression. Now it remains to show that it is impossible. I'm down from Chebyshev to Euler (the series of inverse primes diverges) but, alas, not to Euclid (primes are infinitely many) yet.


This proof for $n=2$ is quasi-elementary (up to Dirichlet's theorem). I hope one can extend it to the general case.

Write $f$ as $f(x,y)=a(x,y)xy+g(x)x+h(y)y+c$. Then one can formulate the problem as follows:

Let an integer $c$ and polynomials $g(x)$, $h(y)$ satisfy the condition: $$ (\forall p\ne q) \ \ p|(h(q)q+c) \vee q|(g(p)p+c) $$ Prove that $c=0$, and either $g=0$ or $h=0$ .

Proof. Suppose the opposite. Let $p$ be a prime which does not divide the coefficients of $h$, does not divide $c$ and $p>{\rm deg} h+1$. Since there is only finite number of such primes $q$ that $q|(g(p)p+c)$ (because $c\ne 0$ or $g\ne 0$), then $$ (\exists r\ {\rm prime}\ \forall q>r)\ \ p|(h(q)q+c). $$ By Dirichlet's theorem there are such primes $q_1,\ldots,q_{p-1}>r$ that $q_i\equiv i\mod p$. Then for all $i\ (1\le i \le p-1)\ \ h(i)i+c=k_ip$ with $k_i\in \mathbb{Z}$.

Now consider the system of linear equations $h(i)i+c=k_ip \ (1\le i \le {\rm deg}h+2)$ for the coefficients of $h$ (and $c$). Its determinant is the Vandermonde's determinant. Hence all coefficients (and also $c$) are divided by $p$. Contradiction.

  • 1
    $\begingroup$ Erm... $m$ depends on $A$, $A$ depends on $q$, $q$ depends on $m$. This doesn't look right. Am I misunderstanding something? $\endgroup$
    – fedja
    Nov 20 '11 at 3:48
  • $\begingroup$ @fedja: You are right, thank you. I will think how to correct my answer, but for now delete it $\endgroup$ Nov 20 '11 at 14:48
  • $\begingroup$ Now this is a corrected answer after a remark of fedja $\endgroup$ Nov 28 '11 at 0:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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