Maths Olympiad Prep

Library / /3 of 6

Number theory Difficulty 5.6 AIME, harder Prove it Brazil

Let p(x)p(x) be the polynomial x3+14x22x+1x^3 + 14x^2 - 2x + 1. Let p(n)(x)p^{(n)}(x) denote p(p(n1)(x))p(p^{(n-1)}(x)). Show that there is an integer NN such that p(N)(x)xp^{(N)}(x) - x is divisible by 101101 for all integers xx.

Solution

We have p(x)p(y)=(x3+14x22x+1)(y3+14y22y+1)=(xy)(x2+xy+y2+14x+14y2)p(x) - p(y) = (x^3 + 14x^2 - 2x + 1) - (y^3 + 14y^2 - 2y + 1) = (x - y)(x^2 + xy + y^2 + 14x + 14y - 2). Since 101101 is prime, p(x)p(y)(mod101)xy(mod101)p(x) \equiv p(y) \pmod{101} \Leftrightarrow x \equiv y \pmod{101} or x2+xy+y2+14x+14y20(mod101)x^2 + xy + y^2 + 14x + 14y - 2 \equiv 0 \pmod{101}.

Completing squares, we have
x2+xy+y2+14x+14y20(mod101)(2x+y+14)2+3y2+28y20(mod101)(2x+y+14)23(y29)2(mod101)() \begin{aligned} x^2 + xy + y^2 + 14x + 14y - 2 &\equiv 0 \pmod{101} \\ &\Leftrightarrow (2x + y + 14)^2 + 3y^2 + 28y - 2 \equiv 0 \pmod{101} \\ &\Leftrightarrow (2x + y + 14)^2 \equiv -3(y - 29)^2 \pmod{101} \quad (*) \end{aligned}
By the quadratic reciprocity law, (3101)(1013)=(1)10112312=1(3101)=(23)=1\left(\frac{-3}{101}\right) \cdot \left(\frac{101}{-3}\right) = (-1)^{\frac{101-1}{2} \cdot \frac{-3-1}{2}} = 1 \Leftrightarrow \left(\frac{-3}{101}\right) = \left(\frac{2}{3}\right) = -1, so 3-3 is not a quadratic residue modulo 101101. Thus
()2x+y+14y290(mod101)xy29(mod101) (*) \Leftrightarrow 2x + y + 14 \equiv y - 29 \equiv 0 \pmod{101} \Leftrightarrow x \equiv y \equiv 29 \pmod{101}
Thus p(x)p(y)(mod101)xy(mod101)p(x) \equiv p(y) \pmod{101} \Leftrightarrow x \equiv y \pmod{101}, which means that p(x)p(x) admits an inverse function.

To finish the problem, fix xx and consider x,p(x),p(2)(x),(mod101)x, p(x), p^{(2)}(x), \dots \pmod{101}. Since there are infinite numbers and 101101 remainders, there are mm and nn such that m>nm > n and p(m)(x)=p(n)(x)(mod101)p(mn)x(mod101)p^{(m)}(x) = p^{(n)}(x) \pmod{101} \Leftrightarrow p^{(m-n)} \equiv x \pmod{101}. So for each k(mod101)k \pmod{101} there is a positive integer nkn_k such that p(nk)(k)k(mod101)p^{(n_k)}(k) \equiv k \pmod{101}. Choose N=lcm(n1,n2,,n101)N = \text{lcm}(n_1, n_2, \dots, n_{101}) and we are done.

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.