Maths Olympiad Prep

Library / /89 of 92

Algebra Difficulty 7.6 National olympiad, round 2 Prove it Iran

Find all polynomials with integer coefficients PP such that the set P(Z)={P(a):aZ}P(\mathbb{Z}) = \{P(a) : a \in \mathbb{Z}\} contains an infinite geometric progression.

Solution

Suppose that the image of integer numbers under the polynomial P(x)=anxn+an1xn1++a1x+a0P(x) = a_nx^n + a_{n-1}x^{n-1} + \dots + a_1x + a_0 contains an infinite geometric progression with common ratio aZ{0}a \in \mathbb{Z} - \{0\}. For each bZb \in \mathbb{Z} we have
P(ax+b)=ananxn+(nanan1b+an1an1)xn1+ P(ax + b) = a_n a^n x^n + (n a_n a^{n-1} b + a_{n-1} a^{n-1}) x^{n-1} + \dots
anP(x)=ananxn+an1anxn1++a0an. a^n P(x) = a_n a^n x^n + a_{n-1} a^n x^{n-1} + \dots + a_0 a^n.
We can find some b1,b2Zb_1, b_2 \in \mathbb{Z} and NNN \in \mathbb{N} such that for every xNx \ge N,
P(ax+b2)<anP(x)<P(ax+b1), P(ax + b_2) < a^n P(x) < P(ax + b_1),
and for every xNx \le -N,
P(ax+b2)<anP(x)<P(ax+b1), or P(ax+b1)<anP(x)<P(ax+b2). P(ax + b_2) < a^n P(x) < P(ax + b_1), \ \text{or } P(ax + b_1) < a^n P(x) < P(ax + b_2).
For each P(x)P(x) in the geometric progression, aP(x),a2P(x),,anP(x),aP(x), a^2P(x), \dots, a^nP(x), \dots are all in P(Z)P(\mathbb{Z}), hence there exists some yZy \in \mathbb{Z} such that anP(x)=P(y)a^n P(x) = P(y). If x|x| is sufficiently large (there are infinitely many values of P(x)P(x) in the geometric progression), using the above inequalities, ax+b1<y<ax+b2ax + b_1 < y < ax + b_2. Therefore, yaxy - ax is a constant value between b1b_1 and b2b_2. Hence there exists some constant number cc such that the equation anP(x)=P(ax+c)a^n P(x) = P(ax + c) has infinitely many solutions and consequently P(ax+c)P(ax + c) and anP(x)a^n P(x) are two equal polynomials.
Now, our goal is to find all polynomials P(x)Z[x]P(x) \in \mathbb{Z}[x] satisfying the equation anP(x)=P(ax+c)a^n P(x) = P(ax + c). Let Q(x)=ax+cQ(x) = ax + c. If α\alpha is a root of P(x)P(x), setting x=αx = \alpha in the equation implies that P(Q(α))=0P(Q(\alpha)) = 0 and hence Q(α),Q2(α),Q(\alpha), Q^2(\alpha), \dots are all roots of PP. Since P(x)P(x) has a finite number of roots, there are some natural numbers m1>m2m_1 > m_2 such that Qm1(α)=Qm2(α)Q^{m_1}(\alpha) = Q^{m_2}(\alpha). This implies Qm1m2(α)=αQ^{m_1-m_2}(\alpha) = \alpha, since QQ is injective. Note that if β=c1a\beta = \frac{c}{1-a}, then Q(β)=βQ(\beta) = \beta and hence Qm1m2(β)=βQ^{m_1-m_2}(\beta) = \beta. On the other hand, Qm1m2(x)xQ^{m_1-m_2}(x) - x is a linear polynomial. Therefore, it has at most one root, hence α=c1a\alpha = \frac{c}{1-a} is the only root of P(x)P(x). Consequently, P(x)P(x) has the form r(xpq)n=rqn(qxp)nr(x - \frac{p}{q})^n = \frac{r}{q^n}(qx - p)^n, where p,qp, q and rr are three integers such that (p,q)=1(p, q) = 1.
P(x)Z[x]P(x) \in \mathbb{Z}[x], hence
rqnpnZqnrpn(q,p)=1qnrsZ;r=qns. \frac{r}{q^n} p^n \in \mathbb{Z} \Rightarrow q^n \mid r p^n \overset{(q,p)=1}{\Rightarrow} q^n \mid r \Rightarrow \exists s \in \mathbb{Z}; r = q^n s.
Therefore, we have P(x)=s(qxp)nP(x) = s(qx - p)^n, for some p,q,sZp, q, s \in \mathbb{Z} that (p,q)=1(p, q) = 1.
We claim that each polynomial of this form satisfies the problem's condition. It is enough to show that the polynomial qxpqx - p satisfies the property. This is equivalent to showing the existence of a geometric progression whose elements are all congruent to p-p modulo qq. Obviously, {p(q+1)m}m0\{-p(q+1)^m\}_{m\ge 0} is an example of such progression and this completes our proof.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.