Determine all non-constant polynomials f∈Z[X] with the property that there exists k∈N∗ such that for any prime number p, f(p) has at most k distinct prime divisors.
Problem
Source: Stars of Mathematics 2009
Tags: algebra, polynomial, number theory proposed, number theory
ElChapin
06.01.2010 16:48
Nice problem.
f(x)=nxm
Lemma
For each f∈Z[x] let A(f) be the set of prime divisors of f(x) when x runs over the integers. If f has positive degree then A(f) is infinite.
Proof of lemmaThe result is clear for all f with f(0)=0.
Suppose for the sake of contradiction that A(f) is finite for some f with nonzero independent term.
Let P⊆A(f) be the set of primes which divide f(x) for any integer x and let Q=A∖P.
Let b and c be integers such that bc=f(0), (b,c)=1, and p|b for any p∈P.
For each q∈Q there exists an integer rq such that q⧸|f(rq), because of the chinese remainder theorem there exists an integer d with b^2d\equiv r_q\mod q for each q\in Q.
Now f(x)=bc+xg(x) with g(x)\in\mathbb{Z}[x] and f(b^2d)=b(c+bdg(b^2d)).
Since f(b^2d)\equiv r_q\mod q we have that q\not| f(b^2d) for any q\in Q. Also (p,c+bdg(b^2d))=1 for any p\in P, so c+bdg(b^2d) does not have prime factors in A(f).
As there exist inifinitely many such integers d it is sure that for some d, c+bdg(b^2d)\not=\pm 1 so it does have prime factors outside A(f) and this is the contradiction.
(Returning to the problem...) Let f be one such polynomial ( f(p) has at most k disctintc prime divisors) and rewrite it as f(x)=x^mg(x), with g\in\mathbb{Z}[x] and g(0)\not= 0. Suppose for the sake of contradiction that g has positive degree. We can apply the lemma to g so A(g) is inifinite. In particular we can find k+1 primes in A(g) not dividing g(0) and let s be their product. For each of these primes q there exist and integer r_q\not\equiv 0\mod q such that q|f(r_q). By the chinese remainder theorem there exists a\mod s such that a\equiv r_q\mod q for each of these q. Since r_q\not= 0\mod q we have (a, s)=1 then Dirichlet's theorem on primes in arithmetic progressions asures the existence of infinitely many primes p\equiv a\mod s. Choose one of these p such that f(p)\not= 0 and we have that s|f(p) so f(p) has more than k prime divisors, this is a contradiction.
So the only polynomials f\in\mathbb{Z}[x] with the mentioned property are f(x)=nx^m