Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this 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
add comment

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1 Answer

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|improve this answer
add comment

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