Prove that for any $x \in \mathbb N$ such that $x<n!$ is the sum of at most $n$ distinct divisors of $n!$

Prove that every positive integer $x$ with $x<n!$ is the sum of at most $n$ distinct divisors of $n!$.

Solution 1:

Let $x = nq+r$, with $0 \leq r < n$. Note that $x < n!$ implies that $q < (n-1)!$. Now use induction on $q$.

Solution 2:

People do not seem to be going along with my comment. So this is CW, and directly from the answer by Sanchez.

For $n=2,$ we need only 1 divisor of $2!,$ as $1=1.$

For $n=3,$ we need only 2 divisors of $3!=6,$ as $1=1, 2=2,3=3,4=3+1,5=3+2.$

Induction hypothesis: for some $n \geq 2,$ we need at most $(n-1)$ distinct divisors of $n!$ to write any $1 \leq x < n!$ as a sum.

Induction step (Sanchez, above). Let $N = n+1.$ Let $1 \leq x < N! = (n+1)!$ Write $$ x = N q + r, \; \; \mbox{with} \; \; 0 \leq r < N. $$ Because $q < (N-1)! = n!,$ we need at most $(n-1) = (N-2)$ divisors of $n!$ to write $q$ as a sum. So $$ q = \sum_{i=1}^{n-1} d_i, $$ where each $d_i | n!$ Therefore each $Nd_i | N!$

At this stage, we have at most $N-2$ divisors of $N!$ What about $r?$ Well, $r < N,$ so it is automatically a factor of $N!$ So we have finished the decomposition as a sum with at most $(N-1)$ divisors of $N!,$ where $N=n+1.$

CONCLUSION: For all $N \geq 2,$ every integer $1 \leq x < N!$ can be written as the sum of (at most) $N-1$ distinct divisors of $N!$

SUGGESTION: try it for $N=4, \; \; N! = 24.$

NEVER MIND, do it myself. Aliquot divisors 1,2,3,4,6,8,12. $$1=1,2=2,3=3,4=4,5=4+1,6=4+2,7=4+3, 8=8,9=8+1,10=8+2, $$ $$11=8+3, 12= 12, 13 = 12+1, 14 = 12+2, 15 = 12+3, 16 = 12+4,$$ $$17=12+4+1, 18=12+6,19=12+4+3,20=12+8,$$ $$21=12+8+1,22=12+8+2,23 = 12+8+3. $$