# Every number less than $n!$ can be written as a sum of at most $n$ divisors. [duplicate]

Prove that, for every $n > 1$, any number that is less than $n!$ can be written as a sum of at most $n$ distinct divisors of $n!$. [Hint: Use induction and Euclidean division with remainder].

-

## marked as duplicate by Steven Stadnicki, Will Jagy, Ross Millikan, Brian M. Scott, AmzotiMar 28 '13 at 0:06

This question was marked as an exact duplicate of an existing question.

I recommend trying this for some small numbers to get a raw feel for what's going on, say numbers up to 30ish. (And so n up to 5ish.) – anon Mar 20 '13 at 19:28
Presumably, not $n$ up to 30, @anon, that might be messy. :) Presumably, try $n=5$ and $m$ some values bigger than $24$. – Thomas Andrews Mar 20 '13 at 19:30

Outline of induction step on $n$: For any $0\leq m<n!$, apply division by $n$ to get $m=qn+r$ with $0\leq r<n$. Then write $q$ as the sum of at most $n-1$ factors of $(n-1)!$ thus $qn$ as the sum of at most $n-1$ factors of $n!$ and thus $m=qn+r$ as the sum of at most $n$ factors of $n!$.
(We let $0$ be the sum of an empty set of divisors, just for the induction. If you don't like that, you need to deal with the case where $q=0$ - that is, when $m<n$. It's not hard to do.)