Maths Olympiad Prep

Library / /52 of 69

Number theory Difficulty 6.6 National olympiad Prove it Mongolia

A positive integer kk is called nice if there exist positive integers a1,a2,,a2021a_1, a_2, \dots, a_{2021} such that
(1) aiaja_i - a_j is not divisible by 20232023 for any pair 1i<j20211 \le i < j \le 2021,
(2) for any index ii there exists an index jj such that aikaja_i - k a_j is divisible by 20232023.
Find the largest good number kk which is even and less than 100100.

Solution

Answer: 9292.
Set n=2023=7×172n = 2023 = 7 \times 17^2 and denote by Z/nZ\mathbb{Z}/n\mathbb{Z} the set of all residues modulo nn. For any natural number kk, denote by k:Z/nZZ/nZk: \mathbb{Z}/n\mathbb{Z} \to \mathbb{Z}/n\mathbb{Z} the map defined by aa (mod nn) ka\mapsto k a (mod nn).
Assume that kk is nice and a1,a2,,an2a_1, a_2, \dots, a_{n-2} are integers satisfying the two conditions. Then AkAA \subseteq kA by the condition (2), where AA denotes the set
{a1,a2,,an2(modn)}. \{a_1, a_2, \dots, a_{n-2} \pmod{n}\}.
Therefore, A=kA=n2|A| = |kA| = n-2 by the condition 1 and so A=kAA = kA. Since kAkZ/nZkA \subseteq k\mathbb{Z}/n\mathbb{Z} and kZ/nZ=n/(n,k)|k\mathbb{Z}/n\mathbb{Z}| = n/(n,k) we have (n,k)=1(n,k) = 1, whence the map k:Z/nZZ/nZk: \mathbb{Z}/n\mathbb{Z} \to \mathbb{Z}/n\mathbb{Z} is invertible. Thus, by setting B=Z/nZAB = \mathbb{Z}/n\mathbb{Z} \setminus A, we get kB=BkB = B and B=2|B| = 2. More precisely, if B={b1,b2}B = \{b_1, b_2\} then (kb1,kb2)=(b1,b2)(k b_1, k b_2) = (b_1, b_2) or (kb1,kb2)=(b2,b1)(k b_1, k b_2) = (b_2, b_1). Thus (k21)b0(modn)(k^2-1) b \equiv 0 \pmod{n} for some bBb \in B satisfying b0(modn)b \ne 0 \pmod{n} and so (k21,n)1(k^2-1, n) \ne 1.
Now assume that (k,n)=1(k21,n)(k, n) = 1 \ne (k^2 - 1, n). By setting b=n/(k21,n)b = n/(k^2 - 1, n), we choose B={0,b}B = \{0, b\} if kbb(modn)k b \equiv b \pmod{n} and B={b,kb}B = \{b, k b\} if kbb(modn)k b \ne b \pmod{n}. Then the elements of A=Z/nZBA = \mathbb{Z}/n\mathbb{Z} \setminus B satisfy the two given conditions.
Thus, it suffices to find the largest even integer kk such that (k,n)=1(k21,n)(k, n) = 1 \ne (k^2 - 1, n) and k100k \le 100. It is now straightforward to check that 9292 is nice while 100100, 9898, 9696, 9494 are not.

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.