Find all composite positive integers $a{}$ for which there exists a positive integer $b\geqslant a$ with the same number of divisors as $a{}$ with the following property: if $a_1<\cdots<a_n$ and $b_1<\cdots<b_n$ are the proper divisors of $a{}$ and $b{}$ respectively, then $a_i+b_i, 1\leqslant i\leqslant n$ are the proper divisors of some positive integer $c.{}$
Problem
Source: Romania EGMO TST 2024 Day 1 P4, probably unoriginal
Tags: number theory, Divisors
23.08.2024 15:20
what is a proper divisor
23.08.2024 15:22
Nobitasolvesproblems1979 wrote: what is a proper divisor A divisor $d$ of $n$ is called proper if $d \neq n$.
24.08.2024 00:21
OK I understood
24.08.2024 00:28
I think all proper divisors are not included in ai+bi as then 1 is not there
09.12.2024 18:52
oVlad wrote: Find all composite positive integers $a{}$ for which there exists a positive integer $b\geqslant a$ with the same number of divisors as $a{}$ with the following property: if $a_1<\cdots<a_n$ and $b_1<\cdots<b_n$ are the proper divisors of $a{}$ and $b{}$ respectively, then $a_i+b_i, 1\leqslant i\leqslant n$ are the proper divisors of some positive integer $c.{}$ Case 1: $a$ has an odd divisor $a_i$. Then, if $b_i$ is odd, we have $a_i+b_i$ is even, so $a_1+b_1$ is 2, contradiction. Therefore, $b_i$ is even, so $b_1 = 2$. If $a$ also has an even divisor, $a_1$ must be $2$, so $a_1+b_1$ is $4$, contradiction. Therefore, $a$ is odd and $b = 2^k$. We will prove that $k \leq 3$. Assume $k \geq 4$. We have: $a_i \cdot a_{n-i} = a$, for every $i$ And also, $c=(a_i + 2^i)(a_{n-i} + 2^{n-i})$. Expanding this, we get that $2^{n-i}a_i + 2^i a_{n-i}$ is constant. Denote it by $u$. Consider the quadratic: $$x^2 - ux + ab=0$$Its solutions are the pairs $(a_i, a_{n-i})$ which is a contradiction because of the inequality: $a_1<\cdots<a_n$ So we have two cases to check: $b=4$ and $b=8$, which don’t work because every odd number smaller than these is odd. Case 2: $a$ doesn’t have an odd divisor, so it’s a power of two. As we did in case 1, we prove $a=4$ and $a=8$ are the only possible solutions. For $a=4$ pick $b=9$ so $c=25$ works. For $a=8$ pick $b=27$ so $c=65$ works. $\blacksquare$