Given a natural number $n$, call a divisor $d$ of $n$ to be $\textit{nontrivial}$ if $d>1$. A natural number $n$ is $\textit{good}$ if one or more distinct nontrivial divisors of $n$ sum up to $n-1$. Prove that every natural number $n$ has a multiple that is good.
Problem
Source: Own. IMO 2021 Malaysian Training Camp 1
Tags: number theory, Divisors, Perfect Numbers
01.01.2021 18:46
If $n=1$ take $12*1=2+4+6$. If $n>1$ take $6n=n+2n+3n$
01.01.2021 18:56
The nontrivial divisors must sum to $n-1$, not $n$.
01.01.2021 19:39
The motivation is to use perfect numbers. Every number $s=2^{m-1}(2^m-1)$ for an integer $m\ge 2$ is good because \begin{align*}\sum_{i=1}^{m-1} 2^i+\sum_{j=0}^{m-2} 2^j(2^m-1)&=2^{m-1}-2+(2^{m-1}-1)(2^m-1)\\&=2^{m-1}(2^m-1)-1\\&=s-1\end{align*}All summands above are distinct divisors of $s$ since $2^m-1$ is greater than $1$ and odd. Hence it suffices to prove that every positive integer $n$ has a multiple of the form $2^{m-1}(2^m-1)$. Write $n=2^a b$ where $a,b$ are integers and $b$ is odd. Then $m=(a+1)\varphi(b)$ works by Euler's theorem.
02.01.2021 06:26
Here's another idea which uses the fact that $2^n - 1 = 2^{n-1} + ... + 1$. If $n = 2^k$ is a power of $2$ (including $n = 1$), then $6n$ is good, since \[6n - 1 = 6(2^k - 1) + 6 - 1 = (6 \cdot 2^{k-1} + 6 \cdot 2^{k-2} + ... + 6) + 2 + 3.\]So assume $n$ is not a power of $2$. Let $n = 2^k m$, where $k, m$ are integers and $m$ is odd. Also let $2^a$ be the smallest power of $2$ not less than $m$. We claim that $2^x m$ is good for all integers $x \geq a$. Notice that \[(2^x - 1)m = 2^{x-1}m + 2^{x-2}m + ... + m\]and all the summands are different divisors of $2^x m$ that are not powers of $2$. Furthermore, since $m \leq 2^a$ and $m-1$ is even, we can represent $m-1$ as the sum of distinct powers of $2$, all between $1$ and $2^a$ exclusive (look at its representation in base $2$). Therefore, $2^x m - 1 = (2^x - 1)m + (m - 1)$ can be expressed as a sum of distinct nontrivial divisors of $2^x m$, done. To finish, simply take $x$ with $x \geq k$, so $2^x m$ is a multiple of $n$.