Given a polynomial $P(x)=a_{d}x^{d}+ \ldots +a_{2}x^{2}+a_{0}$ with positive integers for coefficients and degree $d\geq 2$. Consider the sequence defined by $$b_{1}=a_{0} ,b_{n+1}=P(b_{n}) $$for $n \geq 1$ . Prove that for all $n \geq 2$ there exists a prime $p$ such that $p$ divides $b_{n}$ but does not divide $b_{1}b_{2} \ldots b_{n-1}$.
Problem
Source:
Tags: algebra, polynomial, number theory
15.04.2018 22:53
It's not hard to prove that: for every prime number $p$ that $p\mid b_n$ for some $n$, there exists index $i_0$ that $p\mid b_{i_0}$ and $p\nmid b_j$ for all $1\leq j<i_0$, and For all $n$ that $p\mid b_n$, we have $i_0\mid n$ and $\nu_p (b_n)=\nu_p (b_{i_0}).$ Note that this also implies $b_m\mid b_n$ for all $m\mid n$. Now, back to the problem, suppose for every prime $p\mid b_n$, there exists $1\leq i<n$ that $p\mid b_i$. If there exists prime number $a$ that $\nu_a (n)\geq 2$, we get that $d\mid \frac{n}{a}$ for all proper divisor $d$ of $n$. This gives $\nu_p (b_{\frac{n}{a}}) =\nu_p (b_n)$ for all $p\mid b_n$. So, $b_{\frac{n}{a}} \geq b_n$. But it's clear that the sequence is strictly increasing, hence contradiction, done. If there's no such prime divisor $a$, i.e. $n$ can be written as product of distinct prime numbers. If $n$ is prime, we get that $\nu_p (b_1)=\nu_p (b_n)$ for all $p\mid b_n$. So, $b_1\geq b_n$, contradiction. Now, we're left with the case that $n$ has two distinct prime factors, say they're $u$ and $v$. We get that $d\mid \frac{n}{u}$ or $d\mid \frac{n}{v}$ for all proper divisor $d$ of $n$. Hence, for all $p\mid b_n$, either $\nu_p (b_{\frac{n}{u}}) =\nu_p (b_n)$ or $\nu_p (b_{\frac{n}{v}}) =\nu_p (b_n)$. This gives $$b_n\leq \mathrm{lcm} (b_{\frac{n}{u}} ,b_{\frac{n}{v}} )=\frac{ b_{\frac{n}{u}}b_{\frac{n}{v}}}{\gcd (b_{\frac{n}{u}},b_{\frac{n}{v}})}\leq b_{\frac{n}{u}}b_{\frac{n}{v}}.$$But it's clear that $b_{i+1}> b_i^2$ for all $i$, so $b_n>b_{\frac{n}{u}}b_{\frac{n}{v}}$, this contradict the above inequality, done.
16.04.2018 03:49
Just copy solution of ISL 2014 N7.
16.04.2018 08:55
btw, just to give an alternate way to ThE-dArK-lOrD's sol from 1) $p\mid b_{i_0}$ and $p\nmid b_j$ for all $1\leq j<i_0$, and 2) For all $n$ that $p\mid b_n$, we have $i_0\mid n$ and $\nu_p (b_n)=\nu_p (b_{i_0}).$ supposes we look at $b_n$. for every prime $p\mid b_n$, there exists $1\leq i<n$ that $p\mid b_i$ ,indeed $i\mid n$ we pair up each prime that divides $b_n$ with the index given by 1) condition ; note that the index divides $n$ hence, it is at most $\frac{n}{2}$ since $\nu_p (b_n)=\nu_p (b_{i_0}).$ the product of $b_i$ that include in the pairing must be not less than $b_n$ Hence, we must have $b_1b_2b_3...b_{\frac{n}{2}} \geq b_n$ but $b_{i} < b_{\frac{n}{2}}$ for $i < \frac{n}{2}$ . Thus $b_1b_2b_3...b_{\frac{n}{2}} < (b_{\frac{n}{2}})^{\frac{n}{2}}$ but $b_{i+1} \geq b_{i}^2$ . Hence $b_n > (b_{\frac{n}{2}})^{2^{\frac{n}{2}}}$ Hence $\frac{n}{2} > 2^{\frac{n}{2}}$ Which leads to a contradiction.
05.05.2018 22:24
Very similar to ISL 2014, N7. It is also a generalization of 2016 China TST https://artofproblemsolving.com/community/c6h1212540p6016827
23.10.2020 12:47
Notice that $b_n=P^n(0)$, for convenience assume $b_0=0$. Suppose on the contrary that there exists $n$ such that for every prime divisor of $b_n$ is also a prime divisor of $b_{n-1}b_{n-2}...b_1$. CLAIM 1. For each integer $n$ we have $$b_n>b_{n-1}b_{n-2}...b_1$$Proof. We proceed by induction, the base case is obvious, now we have $$b_n=P(b_{n-1})>b_{n-1}^2>b_{n-1}b_{n-2}...b_1$$by inductive hypothesis. $\blacksquare$ Therefore, there exists some prime $p$ such that $$v_p(b_n)>v_p(b_{n-1}b_{n-2}...b_1)\qquad(1)$$Let $k$ be the smallest positive integer such that $p|b_k$. Let $Q(x)=P^k(x)$. From an order argument we have $k|n$. Now notice that the coefficient of $x$ in $Q(x)$ is $0$, so $v_p(b_{2k})=Q(b_k)=v_p(b_k)$, and inductively we have $v_p(b_n)=v_p(b_k)$, whcih contradicts $(1)$, so we are done.