Olympiad Maths Prep

Track / Stage 9 / 1 of 80 #1881 of 2000

Problem 1881

IMO P2/P5; hard shortlist
Number theory Difficulty 9.0 Prove it Pre-IMO 2017 Mock Exam · Hong Kong · 2017

Find all positive integers a0a_0, a1a_1, a2a_2, b0b_0, b1b_1, b2b_2 such that
a2b2n2+a1b1n+a0b0a_2 b_2 n^2 + a_1 b_1 n + a_0 b_0 divides (a22017n+b2)n2+(a12017n+b1)n+(a02017n+b0)(a_2^{2017n} + b_2)n^2 + (a_1^{2017n} + b_1)n + (a_0^{2017n} + b_0) for any positive integer nn.

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

Suppose that
a2b2n2+a1b1n+a0b0(a22017n+b2)n2+(a12017n+b1)n+(a02017n+b0)(1) a_2 b_2 n^2 + a_1 b_1 n + a_0 b_0 \mid (a_2^{2017n} + b_2)n^2 + (a_1^{2017n} + b_1)n + (a_0^{2017n} + b_0) \quad (1)
We first claim that a0=b0=1a_0 = b_0 = 1. Let nn be a large multiple of a0b0a_0 b_0. Since a0b0a_0 b_0 divides the left-hand side of (1), it also divides the right-hand side and hence a0b0a02017n+b0a_0 b_0 \mid a_0^{2017n} + b_0. This implies a0b0a_0 \mid b_0 and b0a02017nb_0 \mid a_0^{2017n}. This shows a0a_0, b0b_0 have the same prime divisors. Thus, we can take a sufficiently large nn such that a0b0a02017na_0 b_0 \mid a_0^{2017n}. This gives a0b0b0a_0 b_0 \mid b_0. The only possibility is a0=1a_0 = 1, which implies b0=1b_0 = 1.

Let MM be a sufficiently large integer and let n0n_0 be the product of all primes less than MM. Choose any prime divisor pp of
a2b2n02+a1b1n0+1.(2) a_2 b_2 n_0^2 + a_1 b_1 n_0 + 1. \quad (2)
Clearly, (p,n0)=1(p, n_0) = 1. Thus, pMp \ge M. In particular, we have (p,a1a2)=1(p, a_1 a_2) = 1 as MM is large.

Consider any nn such that nn0(modp)n \equiv n_0 \pmod{p}. Then pp divides the left-hand side of (1). This gives
p(a22017n+b2)n02+(a12017n+b1)n0+2.(3) p \mid (a_2^{2017n} + b_2)n_0^2 + (a_1^{2017n} + b_1)n_0 + 2. \quad (3)
We choose nn such that p1np-1 \mid n. Such an nn exists by the Chinese remainder theorem. By Fermat's little theorem, we obtain p(1+b2)n02+(1+b1)n0+2p \mid (1+b_2)n_0^2 + (1+b_1)n_0 + 2. Taking the difference with (3), as (p,n0)=1(p, n_0) = 1, we get
p(a22017n1)n0+(a12017n1)(4) p \mid (a_2^{2017n} - 1)n_0 + (a_1^{2017n} - 1) \quad (4)
for any nn0(modp)n \equiv n_0 \pmod{p}. By taking n1(modp1)n \equiv 1 \pmod{p-1} and n2(modp1)n \equiv 2 \pmod{p-1} respectively, we have
p(a22017×21)(a120171)(a12017×21)(a220171)=(a120171)(a220171)(a22017a12017). p \mid (a_2^{2017 \times 2} - 1)(a_1^{2017} - 1) - (a_1^{2017 \times 2} - 1)(a_2^{2017} - 1) = (a_1^{2017} - 1)(a_2^{2017} - 1)(a_2^{2017} - a_1^{2017}).
Since pMp \ge M is sufficiently large, the right-hand side must be 00. If one of a1a_1, a2a_2 is 11, then (4) implies both are equal to 11. If a1=a2a_1 = a_2, then (4) implies a1=a2=1a_1 = a_2 = 1 or n01(modp)n_0 \equiv -1 \pmod{p}.

We first consider the case a1=a2=1a_1 = a_2 = 1. In that case, (1) becomes b2n2+b1n+1(1+b2)n2+(1+b1)n+2b_2 n^2 + b_1 n + 1 \mid (1+b_2)n^2 + (1+b_1)n + 2 so that b2n2+b1n+1n2+n+1b_2 n^2 + b_1 n + 1 \mid n^2 + n + 1. Note that b2n2+b1n+1n2+n+1b_2 n^2 + b_1 n + 1 \ge n^2 + n + 1. Thus, equality must hold and hence b1=b2=1b_1 = b_2 = 1. One easily checks that a0=a1=a2=b0=b1=b2=1a_0 = a_1 = a_2 = b_0 = b_1 = b_2 = 1 is a solution.

Next, it remains to consider the case n01(modp)n_0 \equiv -1 \pmod{p}. As pp divides (2), this yields pa2b2a1b1+1p \mid a_2 b_2 - a_1 b_1 + 1. Since pp is large, we must have a2b2a1b1+1=0a_2 b_2 - a_1 b_1 + 1 = 0. Then (2) becomes (a1b11)n02+a1b1n0+1=(n0+1)((a1b11)n0+1)(a_1 b_1 - 1)n_0^2 + a_1 b_1 n_0 + 1 = (n_0 + 1)((a_1 b_1 - 1)n_0 + 1). Therefore, instead of choosing any prime pp dividing (2) at the beginning, we choose such a prime pp dividing (a1b11)n0+1(a_1 b_1 - 1)n_0 + 1. Using the same argument, we obtain either the same solution or n01(modp)n_0 \equiv -1 \pmod{p}. In the latter case, we find that p(a1b11)+1p \mid -(a_1 b_1 - 1) + 1. Again, this forces a1b1=2a_1 b_1 = 2 as pp is large. Thus, (a1,b1)=(1,2)(a_1, b_1) = (1, 2) or (2,1)(2, 1). Also, a2b2=a1b11=1a_2 b_2 = a_1 b_1 - 1 = 1 so that a2=b2=1a_2 = b_2 = 1.

Now, by considering n=3n = 3 in (1), we have 162(3)2+(a12017n+b1)(3)+216 \mid 2(3)^2 + (a_1^{2017n} + b_1)(3) + 2. As a1a_1, b1b_1 have different parities, the right-hand side is odd. This is impossible.

Therefore, the only solution is a0=a1=a2=b0=b1=b2=1a_0 = a_1 = a_2 = b_0 = b_1 = b_2 = 1. \square

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