# Factors of n!

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

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

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

This link might help you answer this question (and provide many minutes of interesting reading). The sum of divisor stuff is about half way down ..... Another interesting link is this one ....
• Jan 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!

This link might help you answer this question (and provide many minutes of interesting reading). The sum of divisor stuff is about half way down ..... Another interesting link is this one ....

Not exactly, I need to show that every number not greater than $\displaystyle n!$ can be expressed as a sum of at most $\displaystyle n$ different factors of $\displaystyle n!$.
• Jan 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 $\displaystyle (n+1)!$. Let $\displaystyle x < (n+1)!$. If $\displaystyle x\leq n!$ then by induction there exists distinct $\displaystyle d_i$ so that $\displaystyle x=d_1+...+d_k$. Thus, it is safe to assume that $\displaystyle n!+1\leq x \leq (n+1)! - 1$. The goal is to find a factor(s) $\displaystyle n!\leq d<x$ of $\displaystyle (n+1)!$ such that $\displaystyle x - d \leq n!$ then by induction $\displaystyle x - d = d_1+...+d_k$ where $\displaystyle d_i$ are distinct and $\displaystyle d_i | n!$ thus clearly $\displaystyle d_i| (n+1)!$ and $\displaystyle d > d_i$ thus it is distinct too. Which means $\displaystyle x = d+d_1+...+d_k$.
• Jan 30th 2008, 04:28 AM
Opalg
Quote:

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

Proof by induction on n: the result is true for n=2. Suppose it holds for n, and let $\displaystyle 1\leqslant x\leqslant (n+1)!$. Divide x by n+1, getting a quotient q and a remainder r, so that $\displaystyle x = q(n+1)+r$, where $\displaystyle 0\leqslant q < n!$ and $\displaystyle 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, $\displaystyle q = c_1+c_2+\ldots+c_n$, where the numbers c_j are distinct divisors of n!. Then $\displaystyle x = q(n+1)+r = (c_1+c_2+\ldots+c_n)(n+1) + r$. Define $\displaystyle a_j = c_j(n+1)\;\;(1\leqslant j\leqslant n)$ and $\displaystyle a_{n+1} = r$. These numbers are all distinct (because $\displaystyle 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.
• Jan 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.
• Jun 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??
• Jun 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 $\displaystyle c_j(n+1)$ must be composite. But it's possible that $\displaystyle c_j$ could be 1, and n+1 prime. Also, the "remainder" term r might well be prime.