Determine all non-constant polynomials $ f\in \mathbb{Z}[X]$ with the property that there exists $ k\in\mathbb{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)=nx^m$
Lemma
For each $ f\in\mathbb{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\subseteq A(f)$ be the set of primes which divide $ f(x)$ for any integer $ x$ and let $ Q=A\setminus P$.
Let $ b$ and $ c$ be integers such that $ bc=f(0)$, $ (b,c)=1$, and $ p|b$ for any $ p\in P$.
For each $ q\in Q$ there exists an integer $ r_q$ such that $ q\not| f(r_q)$, 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$