# Factors of n!

• January 29th 2008, 02:59 AM
james_bond
Factors of n!
Prove that $\forall x\le n!$
$x=\sum_{i=1}^kd_i$ where $k\le n$ (and $d_i$ are different factors of the number $n!$).
• January 29th 2008, 03:37 AM
mr fantastic
Quote:

Originally Posted by james_bond
Prove that $\forall x\le n!$
$x=\sum_{i=1}^kd_i$ where $k\le n$ (and $d_i$ are different factors of the number $n!$).

So you basically need to show that the sum of the divisors of n! is always less than or equal to n!

• January 29th 2008, 03:40 AM
james_bond
Quote:

Originally Posted by mr fantastic
So you basically need to show that the sum of the divisors of n! is always less than or equal to n!

Not exactly, I need to show that every number not greater than $n!$ can be expressed as a sum of at most $n$ different factors of $n!$.
• January 29th 2008, 07:07 PM
ThePerfectHacker
This is a proof outline. The proof is on induction on the factorial. It is clearly true for small numbers. We will prove it is true for $(n+1)!$. Let $x < (n+1)!$. If $x\leq n!$ then by induction there exists distinct $d_i$ so that $x=d_1+...+d_k$. Thus, it is safe to assume that $n!+1\leq x \leq (n+1)! - 1$. The goal is to find a factor(s) $n!\leq d of $(n+1)!$ such that $x - d \leq n!$ then by induction $x - d = d_1+...+d_k$ where $d_i$ are distinct and $d_i | n!$ thus clearly $d_i| (n+1)!$ and $d > d_i$ thus it is distinct too. Which means $x = d+d_1+...+d_k$.
• January 30th 2008, 04:28 AM
Opalg
Quote:

Originally Posted by james_bond
Prove that $\forall x\le n!$
$x=\sum_{i=1}^kd_i$ where $k\le n$ (and $d_i$ are different factors of the number $n!$).

Proof by induction on n: the result is true for n=2. Suppose it holds for n, and let $1\leqslant x\leqslant (n+1)!$. Divide x by n+1, getting a quotient q and a remainder r, so that $x = q(n+1)+r$, where $0\leqslant q < n!$ and $1\leqslant r \leqslant n+1$. (Note that this is slightly different from the normal convention. I want the remainder to lie in the range 1 to n+1, rather than 0 to n.)

By the inductive hypothesis, $q = c_1+c_2+\ldots+c_n$, where the numbers c_j are distinct divisors of n!. Then $x = q(n+1)+r = (c_1+c_2+\ldots+c_n)(n+1) + r$. Define $a_j = c_j(n+1)\;\;(1\leqslant j\leqslant n)$ and $a_{n+1} = r$. These numbers are all distinct (because $r\leqslant n+1$ and all the other numbers are greater than n+1), and they are all divisors of (n+1)!.

That completes the inductive step, so the result is proved.
• January 30th 2008, 07:12 AM
ThePerfectHacker
Quote:

Originally Posted by Opalg
(Note that this is slightly different from the normal convention. I want the remainder to lie in the range 1 to n+1, rather than 0 to n.)

If the part r=0 is the thing that bothers you then if you do that way then it still works because if r=0 then you just are not adding anything to the number and the proof still works.
• June 4th 2008, 01:58 PM
duggaboy
a little confused
Proof by induction on n: the result is true for n=2. Suppose it holds for n, and let http://www.mathhelpforum.com/math-he...d1058765-1.gif. Divide x by n+1, getting a quotient q and a remainder r, so that http://www.mathhelpforum.com/math-he...f396952f-1.gif, where http://www.mathhelpforum.com/math-he...82df4850-1.gif and http://www.mathhelpforum.com/math-he...7dd9157d-1.gif. (Note that this is slightly different from the normal convention. I want the remainder to lie in the range 1 to n+1, rather than 0 to n.)

By the inductive hypothesis,
http://www.mathhelpforum.com/math-he...c5461872-1.gif, where the numbers c_j are distinct divisors of n!. Then http://www.mathhelpforum.com/math-he...0e70e550-1.gif. Define http://www.mathhelpforum.com/math-he...2b8e8394-1.gif and http://www.mathhelpforum.com/math-he...fa653b07-1.gif. These numbers are all distinct (because http://www.mathhelpforum.com/math-he...fce1bbaa-1.gif and all the other numbers are greater than n+1), and they are all divisors of (n+1)!.

That completes the inductive step, so the result is proved.

Does this induction prove that the results are composite numbers??
• June 5th 2008, 01:14 AM
Opalg
Quote:

Originally Posted by duggaboy
Proof by induction on n: the result is true for n=2. Suppose it holds for n, and let http://www.mathhelpforum.com/math-he...d1058765-1.gif. Divide x by n+1, getting a quotient q and a remainder r, so that http://www.mathhelpforum.com/math-he...f396952f-1.gif, where http://www.mathhelpforum.com/math-he...82df4850-1.gif and http://www.mathhelpforum.com/math-he...7dd9157d-1.gif. (Note that this is slightly different from the normal convention. I want the remainder to lie in the range 1 to n+1, rather than 0 to n.)

By the inductive hypothesis,
http://www.mathhelpforum.com/math-he...c5461872-1.gif, where the numbers c_j are distinct divisors of n!. Then http://www.mathhelpforum.com/math-he...0e70e550-1.gif. Define http://www.mathhelpforum.com/math-he...2b8e8394-1.gif and http://www.mathhelpforum.com/math-he...fa653b07-1.gif. These numbers are all distinct (because http://www.mathhelpforum.com/math-he...fce1bbaa-1.gif and all the other numbers are greater than n+1), and they are all divisors of (n+1)!.

That completes the inductive step, so the result is proved.

Does this induction prove that the results are composite numbers??

No. It's clearly true that most of the numbers $c_j(n+1)$ must be composite. But it's possible that $c_j$ could be 1, and n+1 prime. Also, the "remainder" term r might well be prime.