Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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].

share|cite|improve this question

marked as duplicate by Steven Stadnicki, Will Jagy, Ross Millikan, Brian M. Scott, Amzoti Mar 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.)

share|cite|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.