Hint

Since $f$ has nonnegative integer coefficients, $f(1) \ne 0$ unless $f = 0$; clearly this satisfies the problem condition so we suppose $f$ is not identically zero. We'll show that for all sufficiently large primes $p$, $p | f(n)$ only if $p | n$. Let $p$ be a prime larger than $f(1)$ (in particular, $p$ does not divide $f(1)$) and suppose $p | f(n)$ for some $n$. That is, \[p | \text{rad}(f(n)) \implies p | \text{rad}(f(n^{\text{rad}(n)}))\] Iterating, \[p | \text{rad}(f(n^{\text{rad(n)}})) \implies p | \text{rad}(f([n^{\text{rad}(n)}]^{\text{rad}(n^{\text{rad}(n)})}))\] Of course, exponentiation does not change the set of prime factors of a number, so $\text{rad}(n^{\text{rad}(n)})$ is simply $\text{rad}(n)$. It follows that $p | \text{rad}(f(n^{\text{rad}(n)^2})$ and so $p | f(n^{\text{rad}(n)^2})$. By a straightforward induction, $p | f(n^{\text{rad}(n)^k})$ for all $k$. Now $p | f(n)$ so $p | f(n + pN)$ for all nonnegative integer $N$. Since $p$ is coprime to all prime factors of $p - 1$, we can choose $N$ so that \[\text{rad}(p - 1) | \text{rad}(n + pN)\] Then from the above, \[p | f([n + pN]^{\text{rad}(n + pN)^k})\] for all $k$ so that for choice of $k$ sufficiently large $p - 1 | \text{rad}(n + pN)^k$. Then unless $p | n$, $[n + pN]^{\text{rad}(n + pN)^k} \equiv 1 \pmod{p}$ so $p | f(1)$, contradiction. It follows that for all sufficiently large primes $p$, $p | f(n)$ only if $p | n$. Write $f(n) = n^sP(n)$ where $P$ is an integer polynomial satisfying $P(0) \ne 0$. Any non-constant integer polynomial has infinitely many (and thus, arbitrarily large) prime factors. Then $P$ must be constant, since otherwise writing $P(n) = qQ(n) + r$ with $r \ne 0$ would force all prime factors of $P(n)$ to divide $r$ which is absurd. Thus either $f(n) = 0$ (see earliest remark) or $f(n) = Cn^s$ for positive integer $C$ and non-negative integer $s$. It's easy to see in these cases that in fact $f(n) | f(n^{\text{rad}(n)})$ so their $\text{rad}$s automatically satisfy the same relation.

Guessing that $f(x)=x^n$ is a solution, it is obvious to take $f(x)=x^ag(x)$ such that $x$ is not a factor of $g(x)$. Since $\text{rad}(f(n))|\text{rad}(f(n^{rad(n)})) \Longleftrightarrow p|f(n) \implies p|f(n^{\text{rad}(n)})$. So, whenever $p|n^ag(n)$, it must also divide $n^{a\text{rad}(n)}g(n^{rad(n)})$. Case I: If $p|n, p \nmid g(0)$, then $p \nmid g(n)$. Case II: If $p|n,p|g(0)$, then $p|g(n)$ and also $p|g(n^{rad(n)}$. Case III: If $p \nmid n, p|g(n) \implies p|f(n) \implies p|f(n^{\text{rad}(n)}) \implies p|g(n^{\text{rad}(n)})$. So, $g$ satisfies all the conditions that $f$ does. Now if $p|g(n)$, then $p|g(n^{\text{rad}(n)}) \implies p|g((n^{\text{rad}(n)})^{\text{rad}(n^{\text{rad}(n)})})$. But $\text{rad}(n^{\text{rad}(n)})=\text{rad}(n)$. Therefore $p|g(n^{\text{rad}(n)^2})$. By induction, whenever $p|g(n)$, we also get $p|g(n^{\text{rad}(n)^k}) \forall k \in \mathbb{N}$. Case I: $p|n, p|g(n) \implies p|g(0)$. Case II: $p \nmid n, p|g(n)$. We shall show that there is a solution to the system of congruences $x \equiv n \pmod{p}$ and $x \equiv 0 \pmod{\text{rad}(p-1)}$. Since $(p-1,p)=1$, therefore $\forall$ primes $q|p-1$, we have $(q,p)=1$. Therefore $(\text{rad}(p-1),p)=1$. Now, take $x=\text{rad}(p-1)(n (\text{rad}(p-1)^{-1}))$ where $\text{rad}(p-1)^{-1}$ denotes its multiplicative inverse $\pmod{p}$ and this is indeed a solution to the system or else, we can say this just be Chinese Remainder Theorem. Take $k$ to be the maximum of the highest powers of primes dividing $p-1$ taken over all primes dividing it. Then $p-1|\text{rad}(x)^k$. Also since $g(x) \equiv g(n) \equiv 0 \pmod{p}$, we have $p|g(x^{\text{rad}(x)^k}) \implies p|g(1)$. It is well known that there are infinitely many primes $p$ such that a non-constant integer polynomial has a zero $\pmod{p}$. So if $g$ is non-constant, there are infinitely many primes dividing at least one of $g(0)$ and $g(1)$ but then there must be infinitely many divisors of one of these. But these are constants and also by assumption $g(0) \neq 0$. So, $g(1)=0$ but $g(1)$ denotes the sum of the co-efficients of $g$ which are non-negative. So, all of them must be $0$. Hence, $g(x)=0 \implies f(x)=0$. Otherwise, $g(x)=c$ and $f(x)=cx^a$ and this is indeed a solution. Therefore, $f(x)=cx^a$ where $c$ is a non-negative integer.

So apparently I was stupid and didn't see that $f$ has "nonnegative integer coefficients", which stumped me on the $f(1) = 0$ case. If $f$ is allowed to have integer coefficients, then what are the solutions to this problem? This problem looks much more difficult, as then $f(x) = x^n - 1$ also works.

Yes, without the restriction on the coefficients the problem is a little harder but more interesting. It is easy to see that product of cyclotomic polynomials works.

Yeah, I was thinking about that too, like expressing $f(x)=x^ag(x)h(x)$, where $g$ is the product of cyclotomic polynomials, and $h$ is not divisible by any cyclotomic polynmoial, but eventually did not manage to get a solution. If you have one, could u please give your full solution.

Sorry, but how does the product of cyclotomic polynomials work? If we let $f(x) = \Phi_6(x) = x^2 - x + 1$, then $f(2) = 3$ so $\text{rad}(f(2)) = 3$ but $\text{rad}(f(4)) = \text{rad}(13) = 13$, and $3$ certainly does not divide $13$. In fact, $\Phi_n(x)$ for all non-prime $n$ fails I believe.

Very straightforward problem. For any $p$, let $C_p$ be the set of congruences mod $p$ such that $p | f(x) \Leftrightarrow x \in C_p$. Firstly, assume we have $x \in C_p$ but $x^a$ isn't in $C_p$ for some $a$. By Dirichlet Theorem and Chinese Theorem we can take $Q=x$ (mod $p$) and $Q=a$ (mod $p-1$), where $Q$ is prime. Let $n=Q$. Then clearly $p|f(n)$ and so $p | f(n^{rad(n)}) = f(n^n)$. But $n^n \equiv x^a$ (mod $p$) by Fermat Little theorem, so contradiction. Therefore we have: $p | f(x) \Rightarrow p|f(x^a)$ for all $x,a$. We can take $g(x)=x^mf(x)$, for some $m$, such that $g$ has a nonzero constant term. Then we see that $p | g(x) \Rightarrow p |x$ or $p | g(x^a)$ for all $x,a$. If $p | g(x)$ and $p | x$ then $p | g(0)$. Otherwise, with $a=p-1$ then $p | g(1)$. So if $p | g(x)$ then $p | g(0)g(1)$. It is well known fact that all non-constant polynomials $P$ have an infinite number of primes which divide $P(u)$ for some $u$. Therefore $g$ is constant and so $f(x)=ax^m$ for some $a,m$. These work, and so we are done. NOTE: To prove this well known fact. For contradiction assume $P$ is a nonconstant polynomial $P(x)=a_nx^n+...+a_1x+a_0$ and assume only $p_1$, ..., $p_k$ are the only primes that divide some $P(u)$. Then, take $u = \prod_{i=1}^k p_i^{v_{p_i}(a_0)+e_i}$ where $e_i \ge 2$ for all $e_i$. For big enough $e_i$, we will have $P(u) > \prod_{i=1}^k p_i^{v_{p_i}(a_0)}$, and so there will exist $i$ such that $p_i^{v_{p_i}(a_0)+1} | P(u)$. It is easy to see that this implies $p_i^{v_{p_i}(a_0)+1} | a_0$, impossible! So we are done.

Nice Problem

Terrific problem! First, if $f$ is constant, there really isn't much to say -- the polynomial satisfies the condition. We consider nonconstant polynomials from this point on. For any prime $q$ and integer $r$, there exists an integer $n$ and an integer $k$ such that \[ n \equiv r \pmod{p} \]and \[ (\operatorname{rad}n)^k \equiv 0 \pmod{p-1} \]This is not very difficult. Let $j = \operatorname{rad}(p-1)$ and observe that it suffices to take $n = pj$ for $r = 0$ and $n = g^k j$ for $r \neq 0$, where $g$ is a primitive root and we let $k$ vary, since $j \not \equiv 0 \pmod{p-1}$. Assume that for some prime $p$ and integer $x$, $p \mid f(x)$ but $p \nmid x$. Now, observe that by the above, we can take some integer $q$ where $x \equiv q \pmod{p}$ so $p \mid f(q)$, and \[ p \mid f(q^{\operatorname{rad}(q)}) \cdots \mid f(q^{\operatorname{rad}(q)^k}) \equiv f(1) \pmod{p} \]Hence, for this kind of prime, it must be true that $p \mid f(1)$. Since the polynomial cannot vanish at $1$, it must be true that there are only finitely many such $p$, so call these primes $bad$. By Schur's theorem, since the polynomial is nonconstant, there must be infinitely many primes dividing any term in this polynomial, and only finitely many are $bad$, so we have that $p \mid f(n)$ for $p \mid n$ for infinitely many $p$, so $p \mid f(0)$ infinitely often and hence we have that $f(0) = 0$. Let the lowest degree term of $f(x)$ be $x^m$ and observe that $\gcd{(\frac{f(x)}{x^m}, x)} \le A$ for some constant $A$ independent of $x$. Now for the last insight, take $y = \operatorname{lcm}(1, 2, \cdots A)$ and take $x = yk + 1$, where $k$ is a nonnegative integer. Observe that this forces \[ \gcd{(\frac{f(x)}{x^m}, x)} = 1\], since $x$ is not a multiple of any small primes. This forces $\frac{f(x)}{x^m}$ to be a multiple of bad primes only, or else if $p | \frac{f(x)}{x^m}$ and $x$ was not bad, the $\gcd$ would be a multiple of the prime $p$. Hence, the polynomial $g(x) = \frac{f(x)}{x^m}$ has a finite number of prime divisors, and by the contrapositive of Schur, it must be constant, so $f(x) = cx^m$ and those are all the solutions, as one can easily verify, for positive integers $c$ and $m$.

Beautiful problem indeed! Solution Assume that $f$ is non constant. For brevity, we shall write $r$ function instead of the given $\text{rad}$. We note that $r(n^l)=r(n)$ and if $a \mid b$ then $r(a) \mid r(b)$. Now, Replacing $n$ by $n^{r(n)}$ in the given divisibility equation and repeating the process $k$ times for any $k>0$, we get that $r(f(n)) \mid r(f(n^{r(n)^k}))$. We consider two cases: Case 1 If $f(0) \not= 0$. Proof Let $m$ be a number such that $p \mid f(m)$ (such an $m$ exists by Schur's Theorem). Let $k \equiv -m \bmod p-1$ be a sufficiently large positive integer. We consider $n=m+pk$. Now, $p \mid r(f(n))$ and $r(f(n^{r(n)^t})) \equiv f(1) \bmod p$ since $n^{r(n)^t} \equiv 1 \bmod p$. This follows since we have $p-1 \mid n$ and $r(p-1) \mid r(n)$ and for a sufficiently large $t$, $p-1 \mid r(n)^t$. The result follows by FLT. Now, this means that $p \mid f(1)$ and since $p$ can be arbitrarily large (by Schur's Theorem) we have $f(1)=0$ which fails to hold for $f$ non zero with non negative integer coefficients. This case is not possible and we move to Case 2 or $f$ is a constant function. Case 2 If $f(0)=0$. Proof Consider the largest integer $a>0$ such that $X^a \mid f(X)$ and write $f(X)=X^a\cdot g(X)$. Now, we repeat the same argument for $g(X)$ as in the previous case, since the new divisibility condition, after cancelling the $r(n)$ factor from both sides becomes $r(g(n)) \mid r(g(n^{r(n)}))$ from where the arguments of Case 1. shall be applied, yielding $g$ as a constant function. We conclude that $f(X)=cX^m$ for $m \ge 0$ and $c \ge 0$ integers are the only solutions, which clearly work.

Let $f(x)=x^n\cdot g(x)$,where $g(0)\not =0$.If $g$ is constant,obviously $c\cdot x^n$ works and so assume $g$ is non-constant.Now plug $n=:p^{\alpha}$ and we have: $$\text{rad}(p^{\alpha n}\cdot g(p^{\alpha}))\mid \text{rad}(p^{\alpha\cdot p n}\cdot g(p^{\alpha\cdot p}))$$. Now $v_p$ of both sides is $1$ and so $\text{rad}(g(p^{\alpha}))\mid \text{rad}(g(p^{\alpha p}))$.Firstly note that $g$ doesn't posses positive root as all coefficients of $g$ are positive as well(in particular $g(1)\not =0$).Now $g$ is non-constant and so by Schur's it has infinitely many prime factors larger than $\max{g(1),g(0)}$.Now take some prime $q$ satisfying the above,there $\exists x$ $f(x)\equiv 0\pmod q$ and as $q>f(0)$ we have $q\not |x$.$q$ has a primitive root $j$ and by CRT pick $p\equiv j \pmod q$ and $p\equiv 0\pmod {q-1}$.There exists $\alpha$ so that $p^{\alpha}\equiv x \pmod q$ and $p^{\alpha\cdot p}\equiv 1\pmod q$ by FLT and as $q\not | f(1)$ we have that $q\not | g(p^{\alpha\cdot p})$ $\implies$ $q\not | \text{rad}(g(p^{\alpha\cdot p}))$ but $q\mid \text{rad}(g(p^{\alpha}))$ a contradiction.So $f(x)=c\cdot x^n$ are the only solutions.

Only $f(x) = cx^d$ works (and they clearly do). Assume in what follows $f$ is nonzero; thus in particular $f(1) > 0$. The heart of the proof is following lemma. Lemma: If $p$ prime divides $f(n)$ but not $n$, then $p \mid f(1)$. Proof. Let $m$ be such that $m \equiv n \pmod p$ and also $m \equiv 0 \pmod{p-1}$. Let $k = \operatorname{rad} m$. Then \[ p \mid f(n) \implies p \mid f(m) \implies p \mid f(m^k) \implies p \mid f(m^{k^2}) \implies \dots \]and thus $p \mid f(m^{k^e})$ for some $e$ large enough that $p-1 \mid k^e$. Then $m^{k^e} \equiv 1 \pmod p$, so $p \mid f(1)$. $\blacksquare$ Call a polynomial stable if it has the property in the lemma. Claim: The only nonzero stable polynomials with ${\mathbb Z}_{\ge 0}$ coefficients are those of the form $cx^d$. Proof. Indeed, if $f(x)$ is stable and $x \mid f(x)$ then $f(x) / x$ is also stable, so let's assume $f(0) \neq 0$. We claim $f$ is constant. If not, then by Schur's theorem there are infinitely many primes $p$ dividing $f(n)$ for some $n$. Now take such a $(p,n)$ with $p \nmid f(0) f(1)$. Then $p \nmid f(0)$ and $p \mid f(n)$ implies $p \nmid n$, contradicting the stable hypothesis. $\blacksquare$

I'm a bit confused. Where it says $rad(n)=p_1p_2...p_k$ where $p_1,p_2,...,p_k$ are all prime factors of $n$, do they mean that $p_1,p_2,...,p_k$ are all of the prime factors of $n$, or do they mean that all of $p_1,p_2,...,p_k$ are prime factors of $n$?

The right way to interpret it would be the latter but in this question, the former is the correct definition of the $rad$ function.

Nice problem. Here's my solution: Call a polynomial $f$ nice if it satisfies the given conditions. Note that all constant polynomials are nice. So from now on assume that $f$ is non-constant. Also notice that the given condition is equivalent to the statement $$p \mid f(n) \Rightarrow p \mid f(n^{\operatorname{rad}(n)}) \quad \forall n \in \mathbb{N} \text{ and primes } p$$Denote this statement by $P(n)$, and suppose $X(n)=n^{\operatorname{rad}(n)}$. We make two cases as follows- CASE 1 $(p \nmid n):$ Let $X^a(n)$ denote the process $X$ applied $a$ times. Then, using the fact that $\operatorname{rad}(X(n))=\operatorname{rad}(n)$, we have $$X^2(n)=X(X(n))=(X(n))^{\operatorname{rad}(X(n))}=(X(n))^{\operatorname{rad}(n)}=n^{(\operatorname{rad}(n))^2}$$Continuing in a similar fashion, we get that $X^a(n)=n^{(\operatorname{rad}(n))^a}$. Now, choose $z>0$ such that $n \equiv z \pmod{p}$ and $p-1 \mid z$. Then $$p \mid f(n) \Rightarrow p \mid f(z) \Rightarrow p \mid f(X(z)) \Rightarrow p \mid f(X(X(z))) \Rightarrow \dots \Rightarrow p \mid f(X^a(z))$$$$\Rightarrow f(X^a(z)) \equiv f(z) \pmod{p} \Rightarrow z^{(\operatorname{rad}(z))^a}=X^a(z) \equiv z \pmod{p} \Rightarrow z^{(\operatorname{rad}(z))^a-1} \equiv 1 \pmod{p}$$This means that for all positive integral values of $a,$ $\operatorname{ord}(z) \mid (\operatorname{rad}(z))^a-1$. But, as $p-1 \mid z$, so we must have $p-1 \mid \operatorname{rad}(z)^a$ for some sufficintly large $a$. This gives $$\operatorname{ord}(z) \mid \gcd((\operatorname{rad}(z))^a-1,(\operatorname{rad}(z))^a)=1 \Rightarrow p \mid n-1 \Rightarrow p \mid f(n)-f(1) \Rightarrow p \mid f(1)$$Thus, for all primes $p$, if $p \mid f(n)$, then $p \mid f(1)$. However, by Schur's Theorem, there exist infinitely many such primes $p$, and so we must have $f(1)=0$, which is only possible if $f$ is the zero polynomial. CASE 2 $(p \mid n):$ As $p \mid f(n)$, so we get $p \mid f(0)$. However, again by Schur's result, we have infinitely many such primes $p$, and so we must have $f(0)=0$. Now, we can take $f(n)=ng(n)$ for some polynomial $g$ with non-negative integral coefficients. One can easily see that if $f$ is nice, then so is $g$. So applying the same analysis on $g$, we get that either $g$ is a constant polynomial, or $g(n)=nh(n)$. Continuing in a similar fashion, we get our final solution as $$\boxed{f(n)=An^B \text{ where } A,B \in \mathbb{N} \cup \{0\}}$$

Nice problem We'll use the following fact throughout the entire solution: \[ \text{rad}(n^k) = \text{rad}(n) \]Now, notice that if $p | n$ and $p | f(n)$, then we have $p | n | f(n) - f(0)$, which gives us $f(0) = 0$. Otherwise, if $p \nmid n$ and $p | f(n)$, we have \[ p | n^{(p - 1) \text{rad}(n)} - 1 | f(n^{(p - 1) \text{rad}(n)}) - f(1) = f(n^{\text{rad}(n)}) - f(1) \]Which gives us $p | f(1)$, since \[ p | \text{rad}(f(n)) | \text{rad}( f(n^{\text{rad}(n)} ) \]Now, consider $f(x) = x^n g(x)$ for some nonzero integer $n$, such that $(g(x), x) = 1$. Since $g(0)$ is a nonzero constant, then we can have infinitely many primes $p \nmid g(0)$ but $p | g(n)$ if $g$ is nonconstant. This gives us $f(0) \not= 0$, but $f(1) = 0$, a contradiction as $f$ is a nonnegative integer coefficient polynomial. Thus, $g$ must be a constant and therefore, we have the solution $$ \boxed{f(n) = cn^d \ \text{where} \ c,d \in \mathbb{Z}_{\ge 0}} $$

The answer is $f(x)=cx^n$, where $c$ and $n$ are nonnegative integers. they obviously works. We are now going to show that they are the only ones. Notice that the condition can be interpreted as, if $p$ is a prime and $n$ is a nonnegative integer then \begin{align} p|f(n)\iff p|f(n^{rad(n)}) \end{align} CLAIM 1. If $p$ is a prime, $n$ and $k$ are nonnegative integers then $$p|f(n)\iff p|f(n^{rad(n)^k})$$Proof. We proceed by induction on $k$. The base case $k=0$ is trivial, while the case $k=1$ is exactly $(1)$. Now suppose this holds for some integer $k$, notice that $rad(n^{(rad(n)^k})=rad(n)$, hence from $(1)$ and the inductive hypothesis we have $$p|f(n)\iff p|f(n^{rad(n)^k})\iff p|f((n^{rad(n)^k})^{rad(n)})\iff p|f(n^{rad(n)^{k+1}})$$This proves CLAIM 1. $\blacksquare$ CLAIM 2. If $p$ is a prime and $q$ is an integer such that (i)$p\nmid q$ and (ii) $p|f(q)$ Then $p|f(1)$ Proof. By Chinese remainder theorem, there exists an integer $n$ such that \begin{align*} n&\equiv q&\pmod p\\ n&\equiv rad(p-1)&\pmod{p-1}\\ \end{align*}Therefore we have $f(n)\equiv f(q)\pmod p$ hence $p|f(n)$. Moreover, $rad(p-1)|rad(n)$. Therefore, there exists an integer $k$ such that $p-1|rad(n)^k$. By CLAIM 1, we have $$p|f(n^{rad(n)^k})$$By Fermat little theorem we have $n^{rad(n)^k}\equiv 1\pmod p$, hence $p|f(1)$ as desired. $\blacksquare$. Now if $f=0$ it is trivial, therefore we may assume $f\neq 0$.Let $f(x)=x^ng(x)$, where $g(x)$ is a polynomial with nonzero constant term $c$. If $g(x)$ is a constant then we are done. Otherwise, it is well-known(by shortlist 09N3), that there exists infinitely many primes $p_1,p_2,...$ such that for each $i\in\mathbb N$,$p_i|g(n_i)$ for some positive integer $n$ CLAIM 3. For each $i$, at least one of the following hold: (i)$p_i|c$ (ii)$p_i|f(1)$ Proof. This is trivial. Notice that if $p_i|n_i$ then $0\equiv f(n_i)\equiv c\pmod{p_i}$. Otherwise we have $p_i|f(1)$ by CLAIM 2. $\blacksquare$ Now notice that $g$ has nonnegative integer coefficients hence $f(1)\geq 1$. Therefore there are only finitely many primes satisfying at least one of (i) and (ii), contradiction.

Obviously $f(n)=0$ for all $n$ works$.$ Assume that $f$ is non-zero$.$ Let $$f(n)=n^tg(n),$$where $t\in \mathbb{N}_0, g\in \mathbb{N}_0[x], g(0)>0.$ Assume that $\deg(g)\geq 1.$ Now note that by Schur's Theorem$,$ there exists an arbitrarily large prime $p,$ for which there exists a positive integer $n_0,$ for which $$p\mid g(n_0)\mid f(n_0).$$We can assume that $n_0<p,$ because if that's not the case$,$ we can replace $n_0$ by $n_0-p.$ A problem may occur if $n_0=p,$ but then $p\mid g(1),$ which is certainly not possible for large $p.$ Let $n=n_0+lp,$ where $l$ is a positive integer$.$ Notice that $p\mid f(n_0)\equiv f(n)\pmod p.$ We have the following$:$ Claim: If $q\mid f(m)$ for some prime $q$ and positive integer $m,$ then $$q\mid f\bigg(m^{\text{rad}(m)^{k}}\bigg)$$for all positive integers $k.$ Proof: By the given condition$,$ we have $q\mid f(m^{\text{rad}(m)}).$ Iterating this one more time$,$ we get $$q\mid f\bigg((m^{\text{rad}(m)})^{\text{rad}(m^{\text{rad}(m)})}\bigg)=f\bigg(m^{\text{rad}(m)^{2}}\bigg),$$since $\text{rad}(m^a)=\text{rad}(m)$ for all positive integers $a.$ We see that we can iterate this any number of times we want$,$ thus proving the claim$.$ Let's return to the original problem$.$ Since $p\mid f(n),$ by the claim it must also be true that $$p\mid f\bigg(n^{\text{rad}(n)^{k}}\bigg)\equiv f\bigg(n_{0}^{\text{rad}(n)^{k}}\bigg)\pmod p$$for some large positive integer $k,$ which we will choose very soon$.$ Our aim from here is to make the expression $\text{rad}(n)^k$ divisible by $p-1,$ because then it would follow that $p\mid f(1)$ $\hspace{0.5cm}$ (by Fermat's Theorem and the fact that $\gcd(n_0, p)=1$)$.$ Let's look at the factorisation of $p-1:$ $$p-1=p_1^{\alpha_{1}}\cdots p_s^{\alpha_{s}}.$$Since $n=n_0+lp$ and $\gcd(p_i, p)=1$ for all $i,$ we can make $n$ divisible by $p_1\cdots p_s$ due to the Chinese Remainder Theorem$.$ The last thing we need to do is to ensure that $k\geq \max\{\alpha_{1},\cdots \alpha_{s}\}.$ With the choices we made$,$ it is easily seen that $p\mid f(1),$ which is a contradiction$,$ because $p$ can be arbitrarily large$.$ But this means that $\deg(g)=0,$ therefore $$f(n)=c\cdot n^t$$for some $c, t\in \mathbb{N}_0.$ This polynomial is easily verified to be a solution and we are done$.$ $\blacksquare$

lyukhson wrote: 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$. All constant functions $f$ work, so let us say that $f$ is not a constant function. It can be seen that if a prime $p \mid n$ and $p \mid f(n)$, then $p \mid f(n) - f(0) \implies p \mid f(0)$. If a prime $p \nmid n$ and $p \mid f(n)$, then consider a number $m$ such that $p \mid m - n$ and $p-1 \mid m$. Then, $p \mid f(n) \implies p \mid f(m^{\text{rad}(m)^x})$ for any positive integer $x$. This means that, choosing $x$ such that $\text{rad}(m)^x$ is divisible by $p-1$, we get that $p \mid f(m^{\text{rad}(m)^x})$ $ \equiv f(m^{p-1}) \equiv f(1) \pmod{p} \implies p \mid f(1)$. Due to Schur's Theorem, there exists infinitely many primes $p$ such that $p \mid f(n)$. If $f(x)=x^nf_1(x)$ for some function $f_1$ with non-zero constant term, then $f_1(0)$ is also a valid solution, so we reduce all working polynomials $f$ to polynomials with non-zero constant term, namely $f_1(x)$. We see that if $f_1(x)$ is non-constant, then infinitely many primes $p$ either divide $f_1(1)$ or $f_1(0)$ as established earlier. But $f_1(0), f_1(1) > 0$ as the constant term is non-zero and the polynomial has non-negative co-efficients, a contradiction. Therefore $f_1(x)$ is a constant function establishing that $\boxed{f(x) = cx^d}$ for all non-negative integers $x$ is the only family of valid non-constant solutions for $f$. It can be verified that these functions indeed work.

The answer is $f(x) = cx^k$, which clearly works. Let $f(x) = x^dg(x)$ with $g(x)$ having nonzero constant term (Unless $f(x) = 0$, which is already covered in solution set), so we have $g(0) \neq 0$. Also, $g(1) \neq 0$ because nonnegative coefficients. Note that $g$ also satisfies the condition given so we may replace $f(x)$ with $g(x)$ Suppose a prime $p$ divides $f(n)$ but not $n$, then we have $p | f(n+pk)$ also, so $p | f(n^{\text{rad}(n+pk)})$. Write $n = g^k$ for some primitive root $g$ and look at the exponent. note that from $k$, we can make it jump to a multiple of $rk$ for any squarefree $r$ by just picking $k$ such that $r | n+pk$. So, eventually, we can ensure that the exponent is divisible by $p-1$ and so $p | f(n^{p-1}) \implies p | f(1)$. Since $f(1) \neq 0$, there can only be finitely many such primes, ignore them. But by Schur's theorem, we know that if $f$ is nonconstant, then there exist infinitely many prime divisors of $f$. But since if $p | f(n)$, either $p | n$ or $p | f(1)$, this is impossible since $x \nmid f(x)$. Therefore, $f$ is constant. Scaling back by $x^k$, we get the solution set $f(x) = cx^k$, as desired. $\blacksquare$

Nice problem.

There's another way to solve this problem. The idea is to show that if $\zeta$ is a root of $f$, then so is $\zeta^d$ for any positive integer $d$. This was Solution 2 in the official shortlist booklet.

I'm surprised this solution isn't more common because it seemed exceedingly natural to me. My original solution was a fakesolve. I have adapted the idea to what I believe is a legitimate solution that is both long and convoluted The answer is $f(x)=cx^d$ for $c,d \geq 0$ which clearly works. Note that if $f(x)=xg(x)$ works then it is clear that $g(x)$ works as well, so WLOG suppose that $x \nmid f(x)$ and that $f$ is nonconstant: we will prove that there are no solutions. Claim: $\mathrm{rad}(f(s^{s^k}))$ is unbounded for squarefree $s$. Proof: Suppose that this sequence is bounded, so it must be eventually constant by the $\mathrm{rad}$ divisibility condition. On the other hand, I claim that for any $a$, there exists some $b$ such that $f(s^{s^b})$ has a prime divisor which $f(s^{s^a})$ doesn't. Indeed, pick some $Q$ such that $\nu_q(Q)>\nu_q(f(s^{s^a}))$ for all $q \nmid s$. Then select some $b$ such that $\varphi(\varphi(Q)) \mid b-a$ and $b$ is massive such that $\nu_p(f(s^{s^b}))=\nu_p(f(0))$ for all $p \mid s$. We can see that for any prime $q \mid f(s^{s^a})$ and $q \nmid s$, $$a \equiv b \pmod{\varphi(\varphi(Q))} \implies s^a \equiv s^b \pmod{\varphi(Q)} \implies s^{s^a} \equiv s^{s^b} \pmod{Q} \implies f(s^{s^b}) \equiv f(s^{s^a}) \pmod{Q} \implies \nu_q(f(s^{s^b}))=\nu_q(f(s^{s^a})),$$so if $b$ is massive and no primes other than those that divide $f(s^{s^a})$ or $\gcd(f(0),s)$ divide $f(s^{s^b})$, then we obtain a size contradiction, because the $\nu_p$ of any such prime is bounded either by $\nu_p(f(0))$ or $\nu_p(f(s^{s^a}))$, since $b$ is very large.. Hence $f(s^{s^b})$ will have some prime divisor that $f(s^{s^a})$ doesn't, and the sequence can therefore not be eventually constant. Now let $s$ be squarefree and $k\geq 1$ be a fixed integer. Suppose that $\gcd(f(x),f(x^{s^k}))=g(x)$ in the polynomial sense, where $g$ is some integer polynomial. Then for any $n$, $$\gcd(f(n),f(n^{s^k}))\leq Cg(n)$$by Bezout's Lemma, where $\gcd$ here is in the integer sense. On the other hand, by the problem condition and induction we have $$\mathrm{rad}(f(s^{s^a})) \mid f(s^{s^a}), f(s^{s^{a+k}}) \implies \mathrm{rad}(f(s^{s^k})) \mid Cg(s^{s^k})$$for all $a \geq 0$. Thus $g$ cannot be constant, because by our claim $\mathrm{rad}(f(p^{p^k}))$ is unbounded. Now we factorize $$f=f_1^{e_1}\cdots f_k^{e_k}$$where $e_i\geq 1$ and $f_i$ are pairwise distinct irreducible nonconstant integer polynomials (that aren't equal to $x$ either). Let $S_{ij}$ denote the set of powers of squarefree integers $m$ such that $f_i(x) \mid f_j(x^m)$. By what we previously proved, every power of a squarefree integer must belong to some set $S_{ij}$ (possibly multiple). Consider some $S_{ij}$ that contains infinitely many elements. Then if $r$ is a root of $f_i$ then $r^m$ is a root of $f_j$ for infinitely many $m$, hence $r$ must be a root of unity (otherwise $f_j$ should have infinitely many roots), since $x \nmid f(x)$. Hence let $a_{ij}$ be an integer such that every root $r$ of $f_i$ has $r^{a_{ij}}=1$ (in fact, because $f_i$ is irreducible, it must be cyclotomic, but this fact turns out to not matter). Let $P$ denote the product of $a_{ij}$ over all infinite $S_{ij}$, so for any $i$ included in an infinite $S_{ij}$, every root $r$ of $f_i$ has $r^P=1$. On the other hand, there are infinitely many $s^k$ (for $s$ squarefree and integer $k$) such that $P \mid s^k$, so one of these must be contained in an infinite $S_{ij}$. In this case, if $r$ is a root of $f_i$, then $r^{s^k}=1$ is a root of $f_j$, so $1$ is a root of $f$. But because $f$ has nonnegative coefficients, any of its real roots must be nonpositive: contradiction. Thus no solutions other than the given ones work, as desired. $\blacksquare$

not bad, not bad at all!

Obviously $f(x) = cx^n$ works. Otherwise: Let $f(x) = x^k(a_0+a_1x+\cdots+a_mx^m)$ and $m \geq 1, a_m \neq 0$. Then take some large prime $q$ such that $q \mid a_0+a_1k+\cdots+a_mk^m$ and $q \nmid k$ (exists by Schur's theorem). Shorthand $g(x) = a_0+a_2x+\cdots+a_mx^m$. Now take $n = (-k \mod q)(q-1)$. Then we have: $$q \mid \textrm{rad}(g(n)) \mid \textrm{rad}(g(n^{\textrm{rad}(n)})) \mid \textrm{rad}(g(n^{\textrm{rad}(n)^2})) \mid \dots$$ So it follows that $q \mid g(n^{a(q-1)})$ for some $a$. However, this means $q \mid a_0 +a_1+\cdots a_m$ by Fermat's little theorem, which is finite and bounded above. This gives contradiction.

nice problem but annoying to write up, although at this difficulty maybe i should learn to expect that The only solutions are $f(x) = cx^n$; this obviously works. Assume that $f$ is not the $0$ polynomial, so $f(1) > 0$. Note that the condition is equivalent to \[p \mid f(n) \iff p \mid f(n^{\text{rad}(n)})\]for all primes $p$. Claim 1: \[ p \mid f(n) \implies p \mid f(n^{\text{rad}(n)^k}) \]for all $k$. Proof. Induct; base case $k = 1$ is trivial. Now \[p \mid f(n^{\text{rad}(n)^k}) \implies p \mid f((n^{\text{rad}(n)})^{\text{rad}(n^{\text{rad}(n)^k})}) \]but $\text{rad}(n^{\text{rad}(n)^k}) = \text{rad}(n)$, so \[p \mid f((n^{\text{rad}(n)})^{\text{rad}(n^{\text{rad}(n)^k})}) \implies p \mid f((n^{\text{rad}(n)^k})^{\text{rad}(n)}) \implies p \mid f(n^{\text{rad}(n)^{k+1}}) \]and we are done. $\blacksquare$ Claim 2: (main claim) Suppose $p \mid f(n)$; then $p \mid f(1)$ or $p \mid n$. Proof. By CRT, one can pick $m \equiv n \pmod{p}$ and $m \equiv \text{rad}(p-1) \pmod{p-1}$; note that \[p \mid f(n) \implies p \mid f(m).\]Now by the definition of $m$, we can pick $k$ so that $p-1 \mid \text{rad}(m)^k$; choosing this value of $k$, we have that \[p \mid f(n) \implies p \mid f(m) \implies p \mid f(m^{\text{rad}(m)^k}) \equiv f(1) \implies p \mid f(1) \]if $p \nmid n$ by claim 1. Hence either $p \mid f(1)$ or $p \mid n$, as desired. $\blacksquare$ Now suppose $f(x) = x^ig(x)$ with $g(0), g(1) > 0$; then $g(x)$ also satisfies the property outlined in claim 2. Now if $g$ is nonconstant, then by Schur's theorem infinitely many primes $p$ divide $g(n)$ for infinitely many $p$; however, if $p > g(1)$ and $p \mid g(n)$, then $p \nmid g(1)$ for these primes $p$, hence $p \mid n$ by claim 2. However, since $g(n) \equiv g(0) \pmod{p}$, $p \mid g(0)$ for infinitely many primes $p > g(1)$, which is a contradiction since we assumed $g(1), g(0) > 0$. Then $g(x) = c$ for some $c$ and scaling up, $f(x) = cx^i$ for some $i$, as desired.

We claim the solution set is all polynomials of the form $c\cdot X^d$ for some nonnegative integers $c$ and $d$, which clearly work. We now prove these are the only solutions. To this end, suppose FTSOC that some polynomial $f$ works and is not of the desired form. Let $d$ be the maximal nonnegative integer such that we can write $f=X^d\cdot g$ with $g$ having nonnegative integer coefficients. Note that such a $d$ exists since $f$ isn't the zero polynomial. Such a polynomial $g$ satisfies $g(0)\ne 0$. Since $g$ is supposed to be non constant, we also have that one of his coefficients is strictly bigger than $0$, so that $g(1)\ne 0$. Thus, by Schur's Theorem, we can find some prime $p\nmid g(1), g(0)$ that divides some value of $g$, say $g(a)$. Note that our choice of $p$ implies that $a$ is non zero modulo $p$. We now let $Q$ be the set of primes that divide $p-1$, and we let $N=\prod_{q\in Q}q$. Note that $p$ obviously isn't in $Q$, so $N$ is non zero modulo $p$. Then, we choose a prime $r$ bigger than every prime in $Q$ such that $r\equiv a\cdot N^{-1}\pmod p$. The existence of such a prime is guaranteed by Dirichlet's Theorem. Finally, we let $M=r\cdot N$. Since $M\equiv a \pmod p$, we have $p\mid g(M)$ and thus $p\mid f(M)$. We now iterate the problem condition $k>\underset{q\in Q}{\max}\{v_q(p-1)\}$ times, so that \[p\mid f(M)\mid f\left(M^{rad(M)^k}\right)\quad (*)\]Note that we have $p-1\mid \prod_{q\in Q}q^k=N^k\mid rad(M)^k$, so by Fermat's little theorem we have $M^{rad(M)^k}\equiv 1\pmod p$ and thus $p\mid f(1)=g(1)$, contradiction. $\blacksquare$

Consider the following claim: Claim: For all $n \in \mathbb{N}$, if prime $p$ divides $f(n)$, then $p \mid n$ or $p \mid f(1)$. Proof. If $p \mid n$, then we're done. Thus we can assume $p \nmid n$ and we'll prove that $p \mid f(1)$. Since $\operatorname{rad}(n) = \operatorname{rad}(n^{\operatorname{rad}(n)})$, so induction on $k$ yields $\operatorname{rad}(f(n)) \mid \operatorname{rad}(f(n^{\operatorname{rad}(n)^k}))$ for all $n \in \mathbb{N}$. It's clear that we can take $m \in \mathbb{N}$ such that $m \equiv 0 (p-1)$ and $m \equiv n (p)$. Thus $p-1 \mid \operatorname{rad}(m)^k$ for large $k$ and since $0 \equiv f(n) \equiv f(m) (p)$, we have $p \mid \operatorname{rad}(f(m)) \mid \operatorname{rad}(f(m^{\operatorname{rad}(m)^k}))$. Thus for large $k$ we have, $m^{\operatorname{rad}(m)^k} \equiv 1 (p)$, hence $p \mid f(1)$. $\blacksquare$ Now let $g(x)$ be a polynomial such that $f(x) = x^kg(x)$ and $x$ is not factor of $g(x)$. Then if $g$ is nonconstant, then Schur's theorem yields there exists a large enough prime $p$ such that there exists $n$ such that $p \mid g(n)$. If $p \mid n$ then $p \mid g(0)$, contradicting the fact that $p$ is large. Thus $p \nmid n$ and $p \mid f(n)$, so claim yields $p \mid f(1)$. Hence $f(1) = 0$, contradicting the fact that $f(x)$ has nonnegative coefficients. Therefore $g(x)$ is constant and $f(x) = cx^k$ for some nonnegative $c$. This completes proof. $\blacksquare$

Firstly, notice that $rad(n^{rad(n)})=rad(n)$, so $$rad(f(n)) | rad(f(n^{rad(n)}) | rad(f(n^{rad(n)^2})) | \ldots | rad(f(n^{rad(n)^k}))$$Now, suppose for some positive integer $n$ and prime $p$, $f(n) \vdots p$, where $n \not \vdots p$. Now we will find $m$, such that $m \equiv n$ (mod $p$) and $rad(m)^k \vdots p-1$ for big $k$: Let's take $m=rad(p-1) q$, where $q$ is any integer, which is $\equiv \frac{n}{rad(p-1)}$ mod $p$. It works Now with this $m$ we know that $p | rad(f(m)) | rad(f(m^{rad(m)^k}))$, so $f(m^{rad(m)^k}) \vdots p$, by Fermat's Little Theorem $m^{rad(m)^k} \equiv 1$ (mod $p$), so $f(1) \vdots p$ Case 1: $f(1)=0$. Then $f(x) \equiv 0$, which works Case 2: $f(1)>0$. Then $p$ can attain finitely many values. Now let $f(x)=x^mQ(x)$, where $Q(0) \neq 0$. Suppose $Q$ is not constant. Then $gcd(Q(n),n)=gcd(Q(0),n) | Q(0)$, only finitely many values, but $Q$ can be divisible by infinitely many primes, which contradicts that we proved that $p$ can attain only finitely many values. Hence, $Q$ is constant Finally, $\boxed{f(x)=cx^k}$, where $c \geq 0$, which works.

Consider $f(x) = x^d g(x)$. Note that, $g(x)$ also satisfies the given conditions. Therefore: WLOG assume that $f(0) \neq 0$. If prime $p|f(n)$ and $p \nmid n$, then: consider a number $m \equiv n \pmod p$ and $m \equiv 0 \pmod {p-1}$. Let $k=rad(m)$ and thus: $p|f(m) \implies p|f(m^k) \implies p|f(m^{k^2}) \implies \cdots p|f(m^{k^t})$. Taking the value of $t$ sufficiently large such that: $k^t \equiv 0 \pmod {p-1}$. Thus, due to FLT, $p|f(1)$. Thus; such primes $p|f(1)$ are finite. If $f$ is a non-constant polynomial, then: by Schur's theorem, there exists infinitely many primes $p$, such that $p|f(n)$ for some $n \in \mathbb N$. Then: either $p|n$ or $p \nmid n$. The latter implies $p|f(1)$, which has finitely possibilities for $p$. Therefore: there are infinitely many numbers $n$ such that: $\gcd(n, f(n)) > 1$. Therefore: the polynomial $h(x) = gcd(x, f(x))$ is not constant (as it has infinitely many prime divisors), which gives $x|f(x)$. But this contradicts that $f(0) \neq 0$. Therefore $f$ is a constant polynomial if $f(0) \neq 0$. Scaling back: $\boxed{f(x) = c x^d}$ are the only solutions.