Maths Olympiad Prep

Library / Brazilian Mathematical Olympiad /70 of 120

Brazilian Mathematical Olympiad

Number theory Difficulty 5.6 AIME, harder Prove it Brazil

Let p(x)p(x) be the polynomial x3+14x2−2x+1x^3 + 14x^2 - 2x + 1. Let p(n)(x)p^{(n)}(x) denote p(p(n−1)(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+14x2−2x+1)−(y3+14y2−2y+1)=(x−y)(x2+xy+y2+14x+14y−2)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)⇔x≡y(mod101)p(x) \equiv p(y) \pmod{101} \Leftrightarrow x \equiv y \pmod{101} or x2+xy+y2+14x+14y−2≡0(mod101)x^2 + xy + y^2 + 14x + 14y - 2 \equiv 0 \pmod{101}.

Completing squares, we have
x2+xy+y2+14x+14y−2≡0(mod101)⇔(2x+y+14)2+3y2+28y−2≡0(mod101)⇔(2x+y+14)2≡−3(y−29)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)⋅(101−3)=(−1)101−12⋅−3−12=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+14≡y−29≡0(mod101)⇔x≡y≡29(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)⇔x≡y(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(m−n)≡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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.