Find all composite odd positive integers, all divisors of which can be divided into pairs so that the sum of the numbers in each pair is a power of two, and each divisor belongs to exactly one such pair. Proposed by Anton Trygub
Problem
Source: Ukrainian Mathematical Olympiad 2024. Day 2, Problem 9.7
Tags: number theory
VicKmath7
21.03.2024 16:15
The answer is $n=15$ only.
First, we claim that $n$ is squarefree. Suppose otherwise and let $n=p^{k}m$ for some odd prime $p$, $k \geq 2$ and $(m, p)=1$. The divisors divisible by $p$ are $\tau(n)-\tau(m)=k\tau(m) > \frac{\tau(n)} {2}$, so some pair contains two numbers divisible by $p$, contradiction. Hence, $n=p_1p_2 \ldots p_k$ is squarefree for odd primes $p_1<p_2<\ldots$. The divisors divisible by $p_i$ are distinct pairs for any $i$, so the product in each pair is $n$.
Next, we claim that $k=2$. Otherwise, $1+p_1p_2\ldots p_k>p_1+p_2p_3 \ldots p_k$ are powers of $2$, so $p_1+p_2p_3 \ldots p_k \mid 1+p_1p_2\ldots p_k$, i.e. $p_1+p_2p_3\ldots p_k \mid p_1^2-1$, which is impossible by size for $k\geq 3$.
Hence, $n=p_1p_2$ and $p_1+p_2=2^{a}$ and $p_1p_2+1=2^{b}$, so $(p_1-1)(p_2-1)=2^{a}(2^{b-a}-1)$ and $(p_1+1)(p_2+1)=2^a(2^{b-a}+1)$. This easily implies that WLOG $2^{a-1} \mid p_1+1, p_2-1$ (since $p_1 \neq p_2 \pmod{4}$ as $a \geq 2$), which means that by size $p_1=2^{a-1}-1, p_2=2^{a-1}+1$ since $p_1+p_2=2^{a}$. The only such pair is $(3,5)$ by modulo $3$, so we are done.