Factors of n!

**james_bond** · January 29th 2008, 02:59 AM

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!$ ).

**mr fantastic** · January 29th 2008, 03:37 AM

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!

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

**james_bond** · January 29th 2008, 03:40 AM

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 $n!$ can be expressed as a sum of at most $n$ different factors of $n!$ .

**ThePerfectHacker** · January 29th 2008, 07:07 PM

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<x$ 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$ .

**Opalg** · January 30th 2008, 04:28 AM

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.

**ThePerfectHacker** · January 30th 2008, 07:12 AM

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.

**duggaboy** · June 4th 2008, 01:58 PM

Proof by induction on n: the result is true for n=2. Suppose it holds for n, and let

. Divide x by n+1, getting a quotient q and a remainder r, so that

, where

and

. (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,

, where the numbers c_j are distinct divisors of n!. Then

. Define

and

. These numbers are all distinct (because

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??

**Opalg** · June 5th 2008, 01:14 AM

Originally Posted by duggaboy

Proof by induction on n: the result is true for n=2. Suppose it holds for n, and let

. Divide x by n+1, getting a quotient q and a remainder r, so that

, where

and

. (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,

, where the numbers c_j are distinct divisors of n!. Then

. Define

and

. These numbers are all distinct (because

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.

Thread: Factors of n!

LinkBack

Thread Tools

Display

Factors of n!

a little confused

Similar Math Help Forum Discussions

factors

Is there a relation between prime factors and total factors?

sum of factors

Factors of 2310 and Factors of 1365

Factors

Search Tags