Number theory olympiad problem

Question

This is a problem I have been tackling recently, but I am unsure how to address it.

A positive integer $n$ is good if there exists a set of divisors of $n$ whose members sum to $n$ and include $1$. Prove that every positive integer has a multiple which is good.

Any help with a solution appreciated.

Answer 1

Hint: try for multiples of the form $2^pn$ where $n$ is odd and $p$ is large.

Full solution:

Let $n$ be an odd integer; there are $a_1 > a_2 > \ldots > a_k=0$ such that $n=\sum_{l=1}^k{2^{a_l}}$. Let $p \geq a_1$, then $2^pn=(2^p-1)n+n=\sum_{l=0}^{p-1}{2^ln}+\sum_{l=1}^k{2^{a_l}}$ so $n2^p$ is good.

Let $A$ be any integer, then $A|B$ for some integer $B$ of the form $2^ab$ where $a \geq 1$, $b \geq 3$ is odd. We know that for large enough $p$, $2^pb$ is good. But for such large enough $p$, $2^ab|2^pb$ so $A|2^pb$ and $2^pb$ is good.