IMO Shortlist 2012,N5

For discussing Olympiad Level Number Theory problems
tanmoy
Posts:312
Joined:Fri Oct 18, 2013 11:56 pm
Location:Rangpur,Bangladesh
IMO Shortlist 2012,N5

Unread post by tanmoy » Wed Dec 28, 2016 7:16 pm

For a nonnegative integer $n$ define $\operatorname{rad}(n)=1$ if $n=0$ or $n=1$, and $\operatorname{rad}(n)=p_1p_2\cdots p_k$ where $p_1<p_2<\cdots <p_k$ are all prime factors of $n$. Find all polynomials $f(x)$ with nonnegative integer coefficients such that $\operatorname{rad}(f(n))$ divides $\operatorname{rad}(f(n^{\operatorname{rad}(n)}))$ for every nonnegative integer $n$.
"Questions we can't answer are far better than answers we can't question"

User avatar
Thanic Nur Samin
Posts:176
Joined:Sun Dec 01, 2013 11:02 am

Re: IMO Shortlist 2012,N5

Unread post by Thanic Nur Samin » Mon Jan 16, 2017 5:40 pm

Lemma: For a positive integer $N$ and a polynomial with nonegative coefficients $W(x)$, if for all prime number $p>N$ and integers $m$, $p|W(m)\Rightarrow p|m$, then $W(x)\equiv cx^e$.

Proof: If $W\equiv 0$ we are done. Otherwise, take $W(x)=x^eV(x)$ so that $x$ is not a factor of $V(x)$. If $V(x)$ is the constant polynomial, then we are done. Otherwise, take $V(x)=xU(x)+c$, where $c=U(0)$. $c$ is definitely a positive integer. Assume that there exists a prime $q>N$ so that $q|V(x)$ but $q\nmid x$. But that would contradict the statement of the lemma, since $W(x)=x^eV(x)$. So $q|V(x)\Rightarrow q|x$. However, that would mean that $q|c$ for all primes $q>N$ which condradicts the fact that $c$ is a positive integer, since that implies that $c=0$.

Now for the original problem. The constant polynomials trivially satisfies all the rules. For nonconstant polynomials, the problem statement essentially means that for prime $p$, $p|f(n)\Rightarrow p|f(n^{\operatorname{rad}(n)})$. Notice that, $\operatorname{rad}(n^{\operatorname{rad}(n)})=\operatorname{rad}(n)$, as powering doesn't change the set of prime factors of a number. Thus $p|f(n^{\operatorname{rad}(n)})\Rightarrow p|f((n^{\operatorname{rad}(n)})^{\operatorname{rad}(n^{\operatorname{rad}(n)})})\Rightarrow p|f(n^{\operatorname{rad}(n)^2})$. By induction, we get $p|f(n^{\operatorname{rad}(n)^k})$.

Now, $p|f(n)\Rightarrow p|f(n+pm)\Rightarrow p|f((n+pm)^{\operatorname{rad}(n+pm)^k})$. Take $m$ such that $p-1|n+m$. Then, $p-1|n+pm$, and for large enough $k$, $p-1|\operatorname{rad}(n+pm)^k$. So we get that $p \nmid n$ and $p|f(n)\Rightarrow p|f(1)$, by Fermat's Little Theorem. Now, by Schur's theorem, since $f$ is nonconstant, it has infinitely many prime divisors. However, unless $f(1)=0$, $f(1)$ has finitely many prime divisors, which would imply that for after a certain positive integer $N$, for $p>N$, $p|f(n)\Rightarrow p|n$ and due to the lemma, all the polynomails of such form so that $f(1)$ not equal to $0$ would be $f(x)=cx^e$.

If $f(1)=0$, then the sum of all coefficients of $f$ would be $0$. But $f$ is a polynomial with nonnegative coefficients, and thus we get that $f\equiv 0$, which also falls under $f(x)=cx^e$.
Hammer with tact.

Because destroying everything mindlessly isn't cool enough.

Post Reply