Let $a, b$ and $n$ be positive integers with $a>b$ such that all of the following hold: i. $a^{2021}$ divides $n$, ii. $b^{2021}$ divides $n$, iii. 2022 divides $a-b$. Prove that there is a subset $T$ of the set of positive divisors of the number $n$ such that the sum of the elements of $T$ is divisible by 2022 but not divisible by $2022^2$. Proposed by Silouanos Brazitikos, Greece
Problem
Source: Balkan MO 2022 P2
Tags: number theory, Balkan Mathematics Olympiad, Divisors
silouan
06.05.2022 15:49
Proposed by me (Silouanos Brazitikos), Greece
oVlad
06.05.2022 16:17
We will solve the general version of the problem: Let $a, b$ and $n$ be positive integers with $a>b$ such that $a^{k-1}$ and $b^{k-1}$ divide $n$ and $k$ divides $a-b$ for a squarefree number $k.$ Prove that there exists a subset $T$ of the set of positive divisors of $n$ such that the sum of the elements of $T$ is divisible by $k$ but isn't divisible by $k^2$. We begin with some optimization. Note that if $d\mid a$ and $d\mid b$ for some $d$ such that $\gcd(d,k)=1$ then it is enough to solve the problem for $a'=a/d$ and $b'=b/d.$ Therefore, we can assume that if $d\mid \gcd(a,b)$ then $\gcd(d,k)\neq 1.$ Case 1: Assume that $\gcd(a,b)\neq 1.$ Let $k=p_1\cdot p_2\cdots p_t.$ It follows that for some indices $i_1,i_2,\ldots,i_s$ we have\[\gcd(a,b)=p_{i_1}^{m_1}\cdot p_{i_2}^{m_2}\cdots p_{i_s}^{m_s}.\]In particular, by letting $p=p_{i_1}\cdot p_{i_2}\cdots p_{i_s}$ we know that $p^{k-1}\mid n.$ Let's choose the set of divisors $T_i=\{p,p^2,\ldots,p^i\}.$ The sum of the elements of $T_i$ is equal to \[S_i=\sum_{j=1}^ip^j=p\cdot\frac{p^i-1}{p-1}\]and since $\nu_{p_{i_1}}(S_i)=\nu_{p_{i_1}}(p)=1$ then $p_{i_1}^2$ will never divide $S_i$ so $k^2$ will never divide $S_i.$ Hence, if $k/p\mid (p^i-1)/(p-1)$ for some $1\leq i\leq k-1$ then $T_i$ satisfies the desired conditions. To achieve this, we can simply enforce that $q\mid i$ for all primes $q\mid \gcd(p-1,k/p)$ and $q-1\mid i$ for all other primes $q\mid k/p.$ Case 2: Assume that $\gcd(a,b)= 1.$ Then, we can make sure that $a^i\neq b^j$ for any $i,j.$ Begin by choosing some $1\leq i\leq k-1$ such that $k\mid 1+b+\cdots+b^{i-1}=(b^i-1)/(b-1).$ We can do this by using the exact same process as we used in case 1, but with $k$ instead of $p/k$ and $b$ instead of $p.$ If $k^2\nmid (b^i-1)/(b-1)$ then the set $\{1,2,\ldots,b^{i-1}\}$ has the desired conditions and we finish. Let's assume that isn't the case, so $k^2\mid (b^i-1)/(b-1).$ Let's look at the set of divisors $S=\{1,a,b^2,\ldots,b^{i-1}\}.$ The sum of the elements of $S$ is equal to $(b^i-1)/(b-1)+(a-b),$ and since $k\mid a-b$ it is divisible by $k.$ Moreover, if $k^2$ does not divide $a-b$ then $k^2\nmid (b^i-1)/(b-1)+(a-b)$ so $S$ has the desired conditions and we finish. Let's assume once more that this isn't the case. Therefore, $k^2\mid a-b.$ In this case, we consider the set of divisors\[S=\{a^{k-1},a^{k-2}b, a^{k-3}b^2,\ldots,b^{k-1}\}.\]The sum of its elements modulo $k^2$ is equal to $ka^{k-1}.$ Since $k\mid a-b$ and $\gcd(a,b)=1$ then $\gcd(a,k)=1$ so because the sum is congruent to $ka^{k-1}$ modulo $k^2,$ it follows that it is divisible by $k$ and not divisible by $k^2,$ as desired.
VicKmath7
06.05.2022 18:26
Can someone confirm this works? I think it's the simplest solution here. Edit: The official solutions are out and the given solution is basically same as mine .
Edit: The first version of the solution works if none of $2$,$3$,$337$ divides $a$ (otherwise we can't directly finish with LTE). Below we will consider the other cases.
Edit 2: Actually if $2022/a$, we can take the set {$2022$}. If at least one of $3$ or $337$ (say $p$) doesn't divide $a$, then still $v_p(S)=1$, as we can apply LTE, and the construction still works. The problem is when $3,337|a$ and $a$ is odd and $n$ is odd, otherwise we still have divisor $2022$. Then $v_2(S)=1$ only if $v_2(a+b)=1$. Ok, but then I will take $(3.337)^i$ for $i=1,2,...2020$, since we have $v_3(n)$ and $v_{337}(n)\geq 2021$. Obviously this sum has $v_3=v_{337}=1$ and is even, so I am finally done.
Ok, first assume $(a, 2022)=(b, 2022)=1$. We seek for divisors which give sum $S=\frac {a^{2022}-b^{2022}} {a-b}$, for which will have $v_3(S)=v_{337}(S)=1, v_2(S)\geq 1$ due to LTE ($v_3(2022)=v_{337}(2022)=v_2(2022)=1$), so we will have $v_{2022}(S)=1$. So it's pretty natural to check whether $a^i.b^{2021-i}$ for $i=0,1,...,2021$ are divisors of $n$ (note that they are distinct, otherwise we get $a^{i-j}=b^{i-j}$ for some $i, j$, so $a=b$). That's equivalent to $iv_p(a)+(2021-i)v_p(b)\leq v_p(n) (*)$ for each prime $p$ that divides both $a$ and $b$ (for the primes that divide exactly one from $a$ and $b$ it's clear since $2021v_p(a)\leq v_p(n)$ for $p | a$ and $2021v_p(b)\leq v_p(n)$ for $p | b$ ). Now let WLOG $v_p(a)\leq v_p(b)$ and we obtain (*) using again $2021v_p(b)\leq v_p(n)$, so we are done.
Another remark: I believe that the construction in the last paragraph of @above's solution works also for $k |a-b$ given that $(k, a)=1$ (as shown in my solution with LTE; I think that the difference is that he doesn't use that $k$ is squarefree in the last paragraph, but with LTE I use it).
GuvercinciHoca
06.05.2022 18:34
If there exist primes $p,q>3$ and $p^{2021}\cdot q^{2021}|n$,
Case.1:
$2| ord_{337}(p)\cdot ord_{337}(q)$
Let that prime be $p.$ Condition implies $337|p^a+1$ for some integer $168\geq a$.
It's easy to check that at least one of these $2$ subsets will work; $T=(1,p^a)$ or $T=(1,p^a,p^{2a},p^{3a},p^{4a},p^{5a}).$
Case.2:
$ord_{337}(p)$ and $ord_{337}(q)$ are both divide $21.$
Now we can take $6\cdot 337=2022$ numbers from the set $A=(p^{42x}\cdot q^{42y} : x,y\geq 0)$ since there are $49\cdot 49= 2401$ elements in it.
It's easy to see why this chose will work.
Assassino9931
07.05.2022 17:46
I hope this works, but anyway honestly it was not a pleasure to do this long and mostly boring case-bash. There certainly are ways to shorten this, but I hope that in the way it is written the arguments are well motivated.
If $2\mid a$, then $\{2^{10}, 2^9, 2^8, 2^7, 2^6, 2^5, 2^2, 2\}$ is with sum $2022$; if $337 \mid a$, then $\{337, 337^2, 337^3, 337^4, 337^5, 337^6\}$ works (since $337 \equiv 1 \pmod {12}$); if $3 \mid a$, then repeated squaring calculations give luckily $3^{84} \equiv -1 \pmod {337}$ and hence $\{3,3^{85}\}$ works (note that $84$ is even, so $3^{84} \equiv 1 \pmod 4$). From now on, as $a\equiv b$ moduli $2$, $3$ and $337$, we may assume that $2,3,337 \nmid a,b$.
There are not really many possible sums one can look at, so naturally let's try to see if we can find $k_1$ and $k_2$ such that $\{a,a^2,\ldots,a^{k_1},b,b^2,\ldots,b^{k_2}\}$ satisfies the requirements. In all cases we will aim to obtain a set of divisors with sum divisible by $2$, $3$ and $337$, as well as to be congruent to $2$ modulo $4$.
If $a\equiv b \equiv 1 \pmod 4$, then we want $k_1 + k_2 \equiv 2 \pmod 4$; if $a\equiv b \equiv 3 \pmod 4$, then we want $k_1$ and $k_2$ to be odd; if $a\equiv 3 \pmod 4$, $b\equiv 1 \pmod 4$, then we want either $k_1$ to be even and $k_2 \equiv 2 \pmod 4$ or $k_1$ to be odd and $k_2 \equiv 3 \pmod 4$; if $a \equiv 1 \pmod 4$, $b\equiv 3 \pmod 4$, then swap the roles of $k_1$ and $k_2$. So overall, if we have $k_1 \equiv k_2 \equiv 3 \pmod 4$, we shall be fine in any case.
For modulo $3$ the situation is as follows - if $a\equiv b \equiv 1 \pmod 3$, we want $k_1 + k_2 \equiv 0 \pmod 3$ and if $a\equiv b \equiv 2 \pmod {3}$ then any odd $k_1$ and $k_2$ would work. So if we additionally impose $k_1 \equiv k_2 \equiv 0 \pmod {3}$, we shall be fine in any case.
Moving on to modulo $337$, if $a\equiv b \equiv 1 \pmod {337}$, then $k_1 + k_2 \equiv 0 \pmod {337}$ suffices; otherwise, we would like $\frac{a}{a-1}(a^{k_1} + a^{k_2} - 2) \equiv 0 \pmod {337}$ which would be enough if $k_1$ and $k_2$ are divisible by the order of $a$ modulo $337$. However, if this order is even we will have big problems since then $k_1 \equiv k_2 \equiv 3 \pmod 4$ would not be possible!
To sum up, up until now we have solved the case when the order of $a$ (and of $b$) modulo $337$ is odd - in this case when $a\equiv b \equiv 1 \pmod 4$ take $k_1=k_2 = 1011$ and when $a\equiv b\not \equiv 1 \pmod {337}$ take $k_1$ and $k_2$ have to be multiples of this order (which is at most $21$ since $a^{336} \equiv 1$ by Fermat and $336 = 2^4 \cdot 3 \cdot 7$), to be multiples of $3$ and to be congruent to $3$ modulo $4$ - so they are uniquely determined modulo $M \leq 21 \cdot 3 \cdot 4 < 2021$ and hence such $k_1$ and $k_2$ indeed exist.
Now how to deal with the case when the order of $a$ modulo $337$ is $2\ell$ for some integer $\ell$? The advantage here is that $0 \equiv a^{2\ell}-1 \equiv (a^{\ell}-1)(a^{\ell}+1)$, which with $a^{\ell} \not\equiv 1$ yields $a^{\ell} + 1 \equiv 0 \pmod {337}$. So we should completely forget about the sums considered in the previous case and instead show that there is an integer $k$ such that $\{1,a^{\ell}, a^{2\ell}, \ldots, a^{k\ell}\}$ satisfies the requirements. Modulo $2$ we are fine when $k$ is odd since we have assumed from before that $a$ is odd. Modulo $337$ the sum is $0$ precisely when $k$ is odd (since $a^{2m\ell} + a^{(2m+1)\ell} = a^{2m\ell}(a^{\ell} + 1)$ is divisible by $337$). Modulo $3$ we want either $k\equiv 2 \pmod 3$ (this is when $a^{\ell} \equiv 1 \pmod 3$) or $\frac{a^{(k+1)\ell} - 1}{a^{\ell} - 1}$ to be divisible by $3$, i.e. $2^{k+1} - 1$ to be divisible by $3$ which is again fine when $k$ is odd. Now we will have problems with modulo $4$ if $a^{\ell} \equiv 3 \pmod 4$, so let's try killing the divisibility by $2022^2$ with modulo $9$ instead. If $a^{\ell} \equiv 1$, we would like $k+1 \not\equiv 0 \pmod 9$, if $a^{\ell} \equiv 2$, we would like $2^{k+1} - 1 \not\equiv 0 \pmod 9$, i.e. $k+1 \not\equiv 0 \pmod 6$, if $a^{\ell} \equiv 4$, we would like $4^{k+1} - 1$ to be not divisible by $27$; similar for $5$, $7$ and $8$ and in all cases even restricting to $k=1$ or $k=5$ is enough.
Can anybody post the official solutions?
laikhanhhoang_3011
08.05.2022 10:13
Let $$d=(a,b), \, a=dm, \, b=dn $$We have: $$ d.(m-n) \, \vdots \, 2022=2.3.337=p_1.p_2.p_3, (*)$$ Case 1: $m-n \, \vdots \, p_i, \, (m-n, \frac{2022}{p_i})=1, \, i \in \left\{1,2,3 \right\} $ So $d \, \vdots \, \frac{2022}{p_i}$ Choose $$T=\left\{\frac{2022}{p_i}m^{p_i-1},\frac{2022}{p_i}m^{p_i-2}n,...,\frac{2022}{p_i}n^{p_i-1} \right\}$$Then $$S=\sum_{x \in T}^{}=\frac{2022}{p_i}.\frac{m^{p_i}-n^{p_i}}{m-n}$$According to LTE, $v_{p_i}(S)=1 \Rightarrow S \not\vdots 2022$ , satisfied. Case 2: $m-n \, \vdots \, p_i.p_j, \, (m-n, p_k)=1, \, i<j \in \left\{1,2,3 \right\} $ So $d \, \vdots \, p_k$ Choose $$T=\left\{p_k.m^{p_i.p_j-1},p_k.m^{p_i.p_j-2}n,...,p_k.n^{p_i.p_j-1} \right\}$$ Case 3: $m-n \, \vdots \, p_1.p_2.p_3$ Choose $$T=\left\{m^{2021},m^{2021}n,...,n^{2021} \right\}$$ Q.E.D
Jalil_Huseynov
10.05.2022 08:34
During contest, after thinking about $2.5$ hours I came with such a long solution. Let $a=dx,b=dy$, where $d=\gcd(a,b)$. Then we have that $d^{2021}x^{2021}y^{2021}\mid n$ and $2022\mid d(x-y)$. Case 1: $\gcd(d,2022)=1$. So we have $x\equiv y\pmod{2022}$. Since $\gcd(x,y)=1$ we get $\gcd(x,2022)=\gcd(y,2022)=1$. Now I will choose divisors of $x^{2021}y^{2021}$ which are divisors of $n$ such that it holds required divisibility condition. Let's work on this $6$ subsets of divisors: $S_1=\{(x^2)^0(y^2)^{336},(x^2)^1(y^2)^{335},\ldots,(x^2)^{336}(y^2)^0\}\\ S_2=\{(x^2)^0(y^2)^{338},(x^2)^1(y^2)^{337},\ldots,(x^2)^{338}(y^2)^0\} \\ \cdots \\S_6=\{(x^2)^0(y^2)^{346},(x^2)^1(y^2)^{345},\ldots,(x^2)^{346}(y^2)^0\}$ Then choose exactly $337$ elements of each set $S_i$ and consider their sum. The sum $S$ will be like $S\equiv 337(t^{336}+t^{338}+\cdots +t^{346})\pmod{2022}$, where $t\equiv x^2\equiv y^2\pmod{2022}$. Obviously $2022\mid S$. And since $x$ and $y$ are odd, $t$ is odd. So $S$ is sum of squares of $2022$ odd numbers. So $S\equiv 2022\equiv 2\pmod{4}$, which means $4\nmid S$. So $2022^2\nmid S$, as desired. Case 2: $337\mid d$. Since $\gcd(x,y)=1$, $337$ doesn't divide at least $1$ of $x,y$. WLOG $337\nmid x$. Since $337x^{2021}\mid n$ we can consider divisors of $337x^{2021}$. Look at sums $T_i$ of elements of subsets of $337x^{2021}$, where $T_i=337\cdot (\sum_{j=1}^{7}x^{2j}-x^{2i})$. Obviously $2022\mid T_i$ for all $i=1,2,...,7$. Assume $2022^2\mid T_i$ for all $i$. Then taking sum of all $T_i$ gives that $337\mid \sum_{j=1}^{7}x^{2j}$ and since $337\mid \sum_{j=1}^{7}x^{2j}-x^{2i}$ we get $337\mid x^{2i}$, which means $337\mid x$, but it's contradiction. So at least $1$ sum doesn't divisible by $2022^2$ and taking this sums finishes this case. Case 3: $\gcd(d,2022)=2$. Since $2022\mid d(x-y)$ we get $1011\mid x-y$. If $2\mid x-y$, then since $2022\mid x-y$, construction that I wrote for Case $1$ finishes. Now assume $2\nmid x-y$. So $1$ of $x,y$ is even, other one is odd. Now take sum $S$ of elements of divisors of $n$, where $S=2x^0y^{1010}+2x^1y^{1009}+\cdots +2x^{1010}y^0$. Since $x\equiv y\pmod{1011}$ we get $1011\mid S$. Also obviously $2\mid S$. So $2022\mid S$. But since $1$ of $x,y$ is even, other one is odd we get $4\nmid S$. So $2022^2\nmid S$ and we are done with this case. Case 4:$\gcd(d,2022)=3$. we get $674\mid x-y$ and if $3\mid x-y$ then take same divisors as in Case $1$. Now assume $3\nmid x-y$. In this case assume that if $3\mid xy$, then WLOG $3\mid x$ and take first $337$ elements of each sets that I noted in Case $1$ and again see that $2022\mid S$,but $4\nmid S$. So we are done with this case. Case 5: $\gcd(d,2022)=6$. So we have $x\equiv y\pmod{337}$. If $2\nmid xy$ then again we can finish with Case $1$. If $2\mid xy$, then WLOG $2\mid x$, $2\nmid y$ and then take subset $T$ of divisors of $n$ like this : $T=\{6x^0y^{336},6x^1y^{335},\ldots, 6x^{336}y^0\}$ and in the same way as Case $3$ get contradiction from $\pmod{4}$. So we are done!
TechnoLenzer
10.05.2022 19:58
$a > b \ge 1 \Rightarrow \exists p$ prime such that $p | a \Rightarrow p^{2021} | n$. Note that $2022 = 2 \cdot 3 \cdot 337$. Case 1: $p = 2$. Let $T = \{2\cdot 1, 2 \cdot 2^2, 2 \cdot (2^2)^2, ..., 2 \cdot (2^2)^{335}\}$. $sum(T) = 2 \cdot \frac{(2^2)^{336} - 1}{2^2 - 1} = 2 \cdot \frac{4^{336} - 1}{3}$. mod 2: $sum(T) = 2 \times$ odd number, so $v_2(sum(T)) = 1$. mod 3: $3 | 3 \Rightarrow$ by Lifting the Exponent (LTE), $v_3(sum(T)) = v_3(4^{336}-1) - v_3(3) = v_3(336) = 1$. mod 337: By Fermat's Little Theorem (FLT), $4^{336} - 1 \equiv 0 \pmod{337}$. $337 \not | 3 \Rightarrow 337 | sum(T)$. Hence, $2 \cdot 3 \cdot 337 = 2022 | sum(T)$, but $2^2 \not | sum(T) \Rightarrow 2022^2 \not | sum(T)$. Case 2: $p = 3$. Let $T = \{3 \cdot 1, 3\cdot 3, ..., 3 \cdot 3^{335}\}$. $sum(T) = 3 \cdot \frac{3^{336} - 1}{2}$. mod 2: $|T| = 336$, so $sum(T)$ is 336 odd numbers, hence even. mod 3: $sum(T) = 3(1 + 3 + 9 + ... + 3^{335}) \equiv 3 \pmod{9}$. Hence, $v_3(sum(T)) = 1$. mod 337: By FLT again, $337 | sum(T)$. Hence, $2022 | sum(T)$, but $3^2 \not | sum(T) \Rightarrow 2022^2 \not | sum(T)$. Case 3: $p = 337$. Let $T = \{337 \cdot 1, 337 \cdot 337, ..., 337 \cdot 337^5\}$. $sum(T) = 337 \cdot \frac{337^6 - 1}{336}$. mod 2: $|T| = 6$, sum of 6 odd numbers is even. mod 3: $3 | 336 \Rightarrow$ by LTE, $v_3(sum(T)) = v_3(6) = 1$. mod 337: $sum(T) = 337 \cdot (1 + 337 + ... + 337^5) \equiv 337 \pmod{337^2}$. Hence, $v_{337}(sum(T)) = 1$. Hence, $2022 | sum(T)$, but $3^2 \not | sum(T) \Rightarrow 2022^2 \not | sum(T)$. Now we assume $p \equiv 1 \pmod{2}$, $p^2 \equiv 1 \pmod{3}$, $p \not \equiv 0 \pmod{337}$. Case 4: $p^2 \not \equiv 1 \pmod{337}$. Let $T = \{1, p^2, (p^2)^2, ..., (p^2)^335\}$. $sum(T) = \frac{(p^2)^{336} - 1}{p^2 - 1}$. mod 2: $|T| = 336$, sum of 336 odd numbers is even. mod 3: $3 | p^2 - 1 \Rightarrow v_3(sum(T)) = v_3(336) = 1$ by LTE. mod 337: By FLT, $337 | sum(T)$. Hence, $2022 | sum(T)$, but $3^2 \not | sum(T) \Rightarrow 2022^2 \not | sum(T)$. Case 5: $p \equiv 1 \pmod{337}$. Let $T = \{1, p, p^2, ..., p^{2021}\}$. $sum(T) = \frac{p^{2022} - 1}{p - 1}$. mod 2: Sum of 2022 odd numbers is even. mod 3: $sum(T) = (1 + p + ... + p^5)(1 + p^6 + ... + p^{2016})$. If $p \equiv 1 \pmod{3}$, $1 + p + .. + p^5 \equiv 1 + 1 + ... + 1 \equiv 6 \cdot 1 \equiv 0 \pmod{3}$, and similarly $p \equiv -1 \pmod{3} \Rightarrow 1 + p + ... + p^5 \equiv 1 - 1 + 1 ... - 1 \equiv 0 \pmod{3}$. Thus $sum(T) \equiv 0 \pmod{3}$. mod 337: LTE means $v_{337}(sum(T)) = v_{337}(2022) = 1$. Hence, $2022 | sum(T)$, but $337^2 \not | sum(T) \Rightarrow 2022^2 \not | sum(T)$. Case 6: $p \equiv -1 \pmod{337}$. Assume all primes dividing $a$ are $-1 \pmod{337}$, otherwise apply cases $1 \to 5$. If $a$ isn't prime, $\exists p, q$ not necessarily distinct such that $pq \equiv 1 \pmod{337}$, $(pq)^{2021} | n$. Now apply Case 5. If $a$ is prime, $b \equiv a \equiv -1 \pmod {337}$, so $b \neq 1$. If $\exists$ prime factor r of $b \not \equiv -1 \pmod{337}$, apply above cases. Else, $r \equiv -1 \pmod{337}$, so apply Case 5 with $pr$. Note that $q \le b < a = p$, so $p, r$ distinct and hence $p^{2021}, r^{2021}$ both divide $n$.
Orestis_Lignos
18.04.2023 22:34
About a year later, let me add the in-contest solution I submitted. The idea is basically the same as in most solutions above, but I'm adding it anyway. Note that in this solution I literally forgot what LTE is, and so proved it via the Binomial Theorem Let $\gcd(a,b)=d$, and $a=dk, b=d\ell$ with $\gcd(k,\ell)=1$. We infer that $2022 \mid d(k-\ell)$. Case 1: $2022 \mid (k-\ell)$. Then, we consider the $2022$ divisors of the form $k^i\ell^{2021-i}$ for $i \in \{0,1,\ldots,2021 \}$. These are indeed divisors of $n$, as ${\rm lcm}(a,b)^{2021} \mid n$, and so $(dk\ell)^{2021} \mid n$. Moreover, they are obviously all distinct, as $k \neq \ell$. Note that $\displaystyle \sum_{i=0}^{2021} k^i\ell^{2021-i} \equiv 2022k^{2021} \equiv 0 \pmod{2022},$ and so what remains is to investigate this sum $\pmod {2022^2}$. Let $k-\ell=2022m$ for a positive integer $m$. Then, $\displaystyle k^i \equiv (\ell+2022m)^{i} \equiv \sum_{j=0}^{i} \binom{i}{j} \ell^j (2022m)^{i-j} \equiv i\ell^{i-1} \cdot 2022m+\ell^i \pmod {2022^2},$ for all $i$, and so we obtain that $\displaystyle \sum_{i=0}^{2021} k^i\ell^{2021-i} \equiv \sum_{i=0}^{2021} (i\ell^{i-1} \cdot 2022m+\ell^i)\ell^{2021-i} \equiv (1+2+\ldots+2021)\ell^{2021} \cdot 2022m+2022\ell^{2021} \pmod {2022^2},$ and so if the sum was divisible by $2022^2,$ then $2022 \mid \ell^{2021}+2021 \cdot 1011\ell^{2021}m,$ hence working $\pmod {337}$ we see that we must have $337 \mid \ell,$ which implies that $337 \mid (k-\ell)+\ell=k$ as well, a contradiction since $\gcd(k,\ell)=1$. Case 2: Now, if $2022 \nmid (k-\ell)$, we have the following subcases: Subcase 2.1: $p=337 \mid d$. Then, we may pick $p^1,p^2,\ldots,p^{2016}$. These all divide $n$, since $p^{2016} \mid d^{2016} \mid a^{2016} \mid n$. Note these divisors are $2016$ in total, and since $p \equiv 1 \pmod 3$, we infer that $\displaystyle \sum_{i=1}^{2016} p^i \equiv 2016 \equiv 0 \pmod 3$ and that $\displaystyle \sum_{i=1}^{2016} p^i \equiv 2016 \equiv 0 \pmod2 $. Moreover, $\displaystyle \sum_{i=1}^{2016} p^i \equiv 0 \pmod p$ and so the sum is divisible by $2 \cdot 3 \cdot p=2022$. If it was divisible by $2022^2$, too, then we would have that $p^2 \equiv p^1+p^2+\ldots+p^{2016},$ which in turn implies that $p^2 \mid p,$ a contradiction. Subcase 2.2: $p=337 \nmid d$. Then, $p$ must divise $k-\ell$ instead, and so $337 \mid k-\ell$ and $2022 \nmid k-\ell$. Consider the $2022$ divisors of $n$ of the form $dk^i\ell^{2021-i}$, for $i \in \{0,1,\ldots,2021 \}$. These are trivially distinct and are indeed all divisors of $n$, as $(dkl)^{2021} \mid n$. Let $\displaystyle S=d\sum_{i=0}^{2021} k^i\ell^{2021-i}$. We claim that $S$ is a multiple of $2022$. Since $p \mid (k-\ell)$, we immediately have that $S \equiv d \cdot 2022k^{2021} \equiv 0 \pmod p$. Now, if $d$ was even then immediately $2 \mid S$, and if not then we should have $2 \mid (k-\ell)$ and so $S \equiv d \cdot 2022k^{2021} \equiv 0 \pmod 2$. Lastly, if $d$ was a multiple of $3$ then immediately $3 \mid S$, and if not then we should have $3 \mid (k-\ell)$ and so $S \equiv d \cdot 2022k^{2021} \equiv 0 \pmod 3$. Therefore, we conclude that $2022=2 \cdot 3 \cdot p \mid S,$ as desired. To finish, we need to prove that $2022^2 \nmid S$. To this end, it is enough to prove that $p^2 \nmid S$, that is $p^2 \nmid \displaystyle \sum_{i=0}^{2021} k^i\ell^{2021-i},$ which is proved as in Case 1 (we are working $\pmod p^2$ now instead). Having covered all cases, we are done.
NoctNight
19.05.2023 13:31
If $2022\mid a,b$ then take $2022\in T$. Otherwise, $2022\nmid a,b$ so set $2022=M$. Since $2022\nmid a,b$, there is one prime $q\in\{2,3,337\}$ such that $q\nmid a,b$ (because $\nu_p(2022)=1$ for these primes). Case 1: $q\in\{3,337\}$. For $0\leq i\leq M-1$ we have: $$\nu_p\left(a^ib^{M-1-i}\right)\leq \max\{\nu_p\left(a^{M-1}\right),\nu_p\left(a^{M-1}\right)\}\leq \nu_p(n)$$for all primes $p$, because $a^{M-1}\mid n$ and $b^{M-1}\mid n$. Therefore, we can choose $$\{a^{M-1}, a^{M-2}b, \cdots, ab^{M-2}, b^{M-1}\}\subseteq T$$which are pairwise distinct since $a\neq b$. Now, this has sum $S=\frac{a^M-b^M}{a-b}$. Note $2022=2\times 3\times 337$. Thus, by Lifting the Exponent, since $\nu_p(a)=\nu_p(a+kM)=\nu_p(b)$ for any $p\mid M$: $$\nu_p(S)=\nu_p\left(\frac{a^M-b^M}{a-b}\right)\geq (M-1)\nu_p(a)+\nu_p(M)\geq \nu_p(M)=1$$so $2022\mid S$. We now show $2022^2\nmid S$. By Lifting the exponent on odd $q$: $$\nu_q(S)=\nu_q\left(\frac{a^M-b^M}{a-b}\right)=\nu_q(M)=1$$so $2022^2\nmid S$ as needed. Case 2: $q=2$. Notice that $3,337\mid a,b$ implies $N=3\times 337\mid a$ so $N^{M-1}\mid n$. Thus, we take $$S'=N+N^2=N(N+1)$$and $2\mid S'$ since it is the product of two consecutive numbers, so $2022=2N\mid S'$. But $\nu_3(S')=\nu_3(N(N+1))=1$ so $2022^2\nmid S'$, completing the proof.
Ihatecombin
21.12.2024 07:10
Fun problem I was using this for training purposes and decided to actually write the proof down during the solving process to keep track of the solution, so in order for it to not just rot in my files I'll put it here. The solution uses an L.T.E construction.
We will prove that if any one of $a,b$ is not relative prime with $2022$, then there exists a subset $T$. I'm sure there is a better construction but I can't think of one so this is my rather complicated one lol, WLOG $a$ has a common divisor $d$ with $2022$. Let $\cfrac{2022}{d} = y$. If $y = 1$, then it is trivial we simply just make our subset $T$ have only $2022$ as a member. Else $y > 1$, now notice if $d \equiv 1 \bmod{p}$ (where $p$ is some prime divisor of $y$), then by denoting the product of all $p$ as $X$, then we clearly have $d \equiv 1 \bmod{X}$ and thus
\[X \mid 1 + d + \cdots + d^{X-1}\]After this, taking the subset as the expansion of the product
\[\dfrac{dy}{X}(1 + d + \cdots + d^{X-1})\]works due to the fact that $1 + d + \cdots + d^{X-1} \equiv 1 \bmod{d}$ and thus the product will be divisible by $d$ but not $d^2$. Else if there is no such $p$ then notice that
\[y \mid 1 + d + d^2 + \cdots + d^{\phi(y) - 1}\]However the above sum is not divisible by $d$, then simply taking the subset as each term of the sum
\[d + d^2 + \cdots + d^{\phi(y)}\]works.
Now we consider the case where both $a$ and $b$ are relatively prime to $2022$. We claim that the set which is composed of the expansion of the terms of the product $(a^{1010} + 1)(a^{1010} + a^{1009}b + a^{1008}b^2 + \cdots + b^{1010})$ works. Notice that
\[a^{1010} + a^{1009}b + a^{1008}b^2 + \cdots + b^{1010} = \dfrac{a^{1011} - b^{1011}}{a-b}\]and according to L.T.E this has $v_3$ and $v_{337}$ both equal to $1$. We also clearly have $2 \mid a^{1010} + 1$. Thus it is clear that the sum of all the elements in that set is divisible by $2022$, however because $a^{1010} + 1 \equiv 2 \bmod{3}$, the sum is not divisible by $2022^2$. Hence we are done (the fact that each term in the expansion is unique is obvious due to size reasons).