Maths Olympiad Prep

Library / /11 of 12

Number theory Difficulty 6.1 National olympiad Prove it Mongolia

Do there exist positive integers a1,a2,,a2017a_1, a_2, \dots, a_{2017} such that the product
(a12017+a2)(a22017+a3)(a20162017+a2017)(a20172017+a1) (a_1^{2017} + a_2)(a_2^{2017} + a_3) \dots (a_{2016}^{2017} + a_{2017})(a_{2017}^{2017} + a_1)
is a power of a prime with exponent
a) 20172018,2017 \cdot 2018,
b) 20172023.2017 \cdot 2023.

Solution

Assume that there are positive integers a1,a2,,a2017a_1, a_2, \dots, a_{2017} and a prime pp as required. Then, for each ii, there is a positive integer kik_i so that
ai2017+ai+1=pki.() a_i^{2017} + a_{i+1} = p^{k_i}. \qquad (*)
Here a2018=a1a_{2018} = a_1. The sum of all pkip^{k_i} equals to the sum of all ai2017+aia_i^{2017} + a_i which is even and so p=2p = 2.

We claim that aia_i is odd for each ii. Write ai=2αi(2bi+1)a_i = 2^{\alpha_i} \cdot (2b_i + 1) for some integer αi\alpha_i and bib_i. Since ai2017+ai+1=2kia_i^{2017} + a_{i+1} = 2^{k_i} we get 2017αi=αi+12017\alpha_i = \alpha_{i+1} for each ii and so αi=0\alpha_i = 0.
We claim that (a,m)=(1,1)(a, m) = (1, 1) is the only solution of a2017+1=2ma^{2017} + 1 = 2^m. By contrary, there is a solution with m>1m > 1. Then a>1a > 1 and a(22017,2m1)1(mod2m)a^{(2 \cdot 2017, 2^{m-1})} \equiv 1 \pmod{2^m} since a220171(mod2m)a^{2 \cdot 2017} \equiv 1 \pmod{2^m} and a2m11(mod2m)a^{2^{m-1}} \equiv 1 \pmod{2^m}. Thus a21(mod2m)a^2 \equiv 1 \pmod{2^m} and so a212m=a2017+1a^2 - 1 \ge 2^m = a^{2017} + 1 which is a contradiction.
The claim implies that ai>1a_i > 1 for each ii. Indeed, if there is ii so that ai=1a_i = 1 then ai1=1a_{i-1} = 1 by the claim and so ai=ki=1a_i = k_i = 1 for each ii. In this case the sum of all kik_i is 2018.
Thus ai2017+ai+122017+ai+1a_i^{2017} + a_{i+1} \ge 2^{2017} + a_{i+1} and so ki2018k_i \ge 2018. Let k=min(ki)k = \min(k_i). For each 1i20171 \le i \le 2017, it follows from (*) that
ai20172017ai(mod2k). a_i^{20172017} \equiv -a_i \pmod{2^k}.
Since aia_i is odd we get ai(2(201720171),2k1)1(mod2k)a_i^{(2(2017^{2017}-1), 2^{k-1})} \equiv 1 \pmod{2^k} which implies ai261(mod2k)a_i^{2^6} \equiv 1 \pmod{2^k}. Thus ai2622017a_i^{2^6} \ge 2^{2017} and so ki302017k_i \ge 30 \cdot 2017 which means the sum of all kik_i is more than 201720232017 \cdot 2023.

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.