Maths Olympiad Prep

Library / /1 of 7

, 2014

Number theory Difficulty 5.5 AIME, harder Prove it Thailand

Find all polynomials P(x)P(x) with integral coefficients such that
P(n)2557n+(213×2014) P(n) \mid 2557^n + (213 \times 2014)
for all positive integers nn.

Solution

First, we note that the constant polynomials P(x)1P(x) \equiv 1 and P(x)1P(x) \equiv -1 satisfy the above divisibility condition. We show that these two polynomials are the only ones satisfying the divisibility condition.

Suppose that the polynomial P(x)P(x) with the integral coefficients satisfying the above divisibility condition and P(x)1P(x) \neq 1 and P(x)1P(x) \neq -1. Note that P(x)0P(x) \neq 0. If P(Z+){1,0,1}P(\mathbb{Z}^+) \subseteq \{-1, 0, 1\}, then there is a j{1,0,1}j \in \{-1, 0, 1\} such that P(x)jP(x) - j has infinitely many zeros, a contradiction. So there is a positive integer n0n_0 such that P(n0)>1|P(n_0)| > 1. Therefore, there exists a prime number qq such that qP(n0)q \nmid P(n_0) and hence q2557n0+(213×2014)q \nmid 2557^{n_0} + (213 \times 2014). Thus, qq is odd and q2557q \neq 2557 (25572557 is prime). Moreover, note that P(n0+q)P(n0)0(modq)P(n_0+q) \equiv P(n_0) \equiv 0 \pmod{q}. Since P(n0+q)2557n0+q+(213×2014)(modq)P(n_0+q) \equiv 2557^{n_0+q} + (213 \times 2014) \pmod{q}, and P(n0)2557n0+(213×2014)P(n_0) \equiv 2557^{n_0} + (213 \times 2014), q2557n0+(213×2014)(modq)q \equiv 2557^{n_0} + (213 \times 2014) \pmod{q}.
2557n0+q+(213×2014)02557n0+(213×2014)(modq). 2557^{n_0+q} + (213 \times 2014) \equiv 0 \equiv 2557^{n_0} + (213 \times 2014) \pmod{q}.
Thus, 2557n0+q2557n0(modq)2557^{n_0+q} \equiv 2557^{n_0} \pmod{q}. Since (q,2557)=1(q, 2557) = 1, 2557q1(modq)2557^q \equiv 1 \pmod{q}. By Fermat's little theorem, 12557q2557(modq)1 \equiv 2557^q \equiv 2557 \pmod{q}. So q2556q \nmid 2556. But qq is odd, q{3,71}q \in \{3, 71\} which implies that q(213×2014)q \nmid (213 \times 2014). Since q2557n0+(213×2014)q \nmid 2557^{n_0} + (213 \times 2014), q2557n0q \nmid 2557^{n_0} and hence q=2557q = 2557, a contradiction. So we are done. \square

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 reproduced verbatim; metadata (topic, difficulty) added by this project.