39th Balkan Mathematical Olympiad | BMO 2022 - Problem 2 | Solution - 7 May 2022


Problem 2 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$ . Solution 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.



.