A nonconstant polynomial $f$ with integral coefficients has the property that, for each prime $p$, there exist a prime $q$ and a positive integer $m$ such that $f(p) = q^m$. Prove that $f = X^n$ for some positive integer $n$. AMM Magazine
Problem
Source: Romania TST 6 2010, Problem 1
Tags: calculus, integration, algebra, polynomial, modular arithmetic, induction, arithmetic sequence
25.08.2012 19:39
Suppose that for eavery prime $p$ there exists a positive integer $m$ such that $f(p) = p^m$. If $n$ denotes the degree of $f$, then for large primes $p$ we have $f(p) < p^{n+1}$. This implies that there exists a positive integer $m < n+1$ such that $f(p) = p^m$ for infinitely many primes $p$. Therefore $f(X) - X^m$ has infinitely many roots and hence $f(X) = X^m$. Now suppose that there is a prime $p$ such that $f(p) = q^m$ for some prime $q \ne p$ and $m \ge 1$. Since $f$ is nonconstant, there is another prime $l \ne q$, such that $l$ divides $f(k)$ for some integer $k$. By Chinese remainder theorem and Dirirchlet's theorem on primes in arithmetic progression, we can find a prime $r$ such that $r \equiv p \pmod{q}$ and $r \equiv k \pmod{l}$. Then $f(r) \equiv f(p) \equiv 0 \pmod{q}$ and $f(r) \equiv f(k) \equiv 0 \pmod{l}$. Thus $f(r)$ cannot be a power a prime, a contradiction.
31.08.2012 12:24
Let $f(X)=a_nX^n+a_{n-1}X^{n-1}+ \cdots + a_1X+a_0$. Assume that for every prime $p$ there is a positive integer $m$ such that $f(p)=p^m$. We can easily prove by induction that $a_0=a_1= \cdots =a_{n-1} = 0$. Base case: $a_0$ must be divisible by every prime, so $a_0=0$. Inductive step: If $a_0=a_1= \cdots =a_k=0$ for some $k \le n-2$, $f(X)=a_nX^n+a_{n-1}X^{n-1} \cdots a_{k+1}X^{k+1}=X^{k+1}(a_nX^{n-k-1} + a_{n-1}X^{n-k-2} + \cdots + a_{k+1}$. $f(p)$ is a power of $p$ for all primes $p$, so $a_{k+1}$ is divisible by all primes, so $a_{k+1}=0$. So $f(X)=a_nX^n$ where $a_n>0$. Let $X$ be a prime not a factor of $a_n$ implies that $a_n=1$ so $f=X^n$. Assume that there is a prime $p$ such that $f(p)=q^m$ for $p$ not equal to $q$. By Dirichlet's Theorem, there exists infinitely many positive integers $k$ such that $kq^{m+1}+p$ is prime, and let $f(kq^{m+1}+p) = r^t$, Then we can use the fact that $a-b | f(a)-f(b)$ for all integers $a, b$ where $f$ is an integral polynomial, to obtain $q^{m+1} | r^t - q^m$ so $r=q$. It's clearly not possible for $t \ge m+1$, so $t \le m$. But there are infinitely many $k$ such that $kq^{m+1}+p$ is prime, so there exists $1 \le u \le t$ such that $f(X)=q^u$ for infinitely many $X$ which implies $f$ is a constant polynomial. Contradiction.
12.05.2015 09:42
Write $f(X)=X^kg(X),\ k\in \mathbb{N}$ with $g(0)\ne 0$. If $g$ is not constant, by Schur's theorem, it must have an infinite number of prime divisors. Take $p,q>|g(0)|$ be two distinct prime numbers with $p|g(x_1),\ q|g(x_2)$. By CRT and Dirichlet, we find a prime $r$ such that $r\equiv x_1(\mathrm{mod}\ p),\ r\equiv x_2(\mathrm{mod}\ q)$. But $pq|g(r)|f(r)$, hence $f(r)$ cannot be the power of a prime. Thereby, $g$ is constant; looking at primes we get $g\equiv 1$, thereby $f(X)=X^k$.
23.09.2016 10:39
If $f(0) \not= 0$, then choose two primes $r,s>|f(0)|$ such that $r \mid f(a)$ and $s \mid f(b)$ for some integers $a,b$. Clearly, $\gcd(r,a)=\gcd(s,b)=1$ and we can select a prime number $p \equiv a \bmod r$ and $p \equiv b \mod s$, we get that $rs \mid f(p)$, a contradiction! Thus, $f(0)=0$ and $p \mid f(p)$ for all primes $p$. In particular, there exists $m_p$ for each prime number $p$ such that $f(p)=p^{m_p}$; so we get that for large enough prime $p$, $p^{d(f)} \le f(p) <p^{d(f)+1}$ where $d(f)$ is the degree of $f$ and we get that $m_p=d(f)$ for all sufficiently large prime numbers $p$. We get that $f(X)=X^{d(f)}$ has infinitely many roots, hence, $f(X)=X^{d(f)}$ for all $X$.