Find all positive integers $k$ such that for every $n\in\mathbb N$, if there are $k$ factors (not necessarily distinct) of $n$ so that the sum of their squares is $n$, then there are $k$ factors (not necessarily distinct) of $n$ so that their sum is exactly $n$.
Problem
Source: IMOC 2018 N5
Tags: number theory
jasperE3
18.08.2021 07:35
https://aops.com/community/p11390363 kaede wrote: The only possible value of $k$ are $1,2,3,6$ First, we will show that these $k$ satisfy the condition. Suppose that $n$ can be expressed as the sum of $k$ squares of positive divisors of $n$. For $ k=1$, $\quad$ $n=n$ is valid expression, of course. For $ k=2$, $\quad$ $n$ must be even, so $n=n/2+n/2$ is valid expression. For $ k=3$, $\quad$ $n$ must be divisible by $3$, so $n=n/3+n/3+n/3$ is valid expression. For $ k=6$, $\quad$ $n$ must be divisible by $6$, so $n=n/6+n/6+...+n/6$ is valid expression.
If $n$ is odd, then all divisors of $n$ are odd.
If $n$ is not divisible by 3, then all squares of divisors of $n$ are congruent to 1 $\bmod{3}$
Second, we will show that there is no other possible value of $k$. For $k=4$, $\quad$$ n=(2\cdot 7)^{2} +\left(2\cdot 7^{2}\right)^{2} +2\cdot 7^{2}$ cannot be expressed as the sum of $k$ positive divisors of $n$. For $k=5$, $\quad$$ n=\left(7^{2}\right)^{2}+4\cdot 7^{2}$ cannot be expressed as the sum of $k$ positive divisors of $n$. For $k>6$, $\quad$ consider the following two cases (1),(2) (1) $k$ is not divisible by $4$ We can choose an odd $ a\in \mathbb{N}$ such that $\mathrm{min}\left\{d\in \mathbb{N};\ \ d\mid a^{2}\left( a^{2} +k-1\right) ,d >6\right\} >6k$ and $5 \nmid a^{2}\left( a^{2} +k-1\right)$
Use Chinese Remainder Theorem. Also note that $\gcd(k,k+3)\mid 3$
Then $n=a^{2}\left(a^{2} +k-1\right) =\left(a^{2}\right)^{2} +(k-1) a^{2}$ cannot be expressed as the sum of $ k$ positive divisors of $n$.
Assume that $ n$ can be expressed as the sum of $ k$ positive divisors of $ n$.
There exists $ k$ positive divisors of $ n$, $ d_{1} ,d_{2} ,..,d_{k}$ such that $ n=\sum ^{k}_{j=1} d_{j}$ and $ d_{1} \geq d_{2} \geq ..\geq d_{k}$.
Let $ u$ be the smallest positive integer such that $ d_{u} < n/6$ .
(such $ u$ must exist otherwise $ \sum ^{k}_{j=1} d_{j} \geq kn/6 >n)$
Note that $ d_{u} < n/( 6k)$
If $ u=1$, then $ \sum ^{k}_{j=1} d_{j} < k\cdot n/( 6k) < n$, which is impossible.
Suppose that $ u >1$.
Since $ d_{1} +d_{2} +...+d_{u-1} < n$, we have $ d_{1} +d_{2} +...+d_{u-1} \leq 5n/6$
So we have $ \sum ^{k}_{j=1} d_{j} < 5n/6+( k-5) d_{6} < n$, which is also impossible.
(2) $k$ is divisible by $4$ We can choose an odd $ a\in \mathbb{N}$ such that $ \mathrm{min}\left\{d\in \mathbb{N} ;\ \ d\mid a^{2}\left(4a^{2} +k+2\right) ,d >6\right\} >6k$ and $5 \nmid a^{2}\left(4a^{2} +k+2\right)$ Then $n=a^{2}\left(4a^{2} +k+2\right) =\left(2a^{2}\right)^{2} +(2a)^{2} +(k-2) a^{2}$ cannot be expressed as the sum of $ k$ positive divisors of $n$. $\blacksquare$