Results 1 to 8 of 8

Math Help - Factors of n!

  1. #1
    Senior Member
    Joined
    Nov 2007
    Posts
    329

    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!).
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Flow Master
    mr fantastic's Avatar
    Joined
    Dec 2007
    From
    Zeitgeist
    Posts
    16,948
    Thanks
    5
    Quote Originally Posted by james_bond View Post
    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 ....
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Nov 2007
    Posts
    329
    Quote Originally Posted by mr fantastic View Post
    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!.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    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.
    Last edited by ThePerfectHacker; January 30th 2008 at 07:08 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by james_bond View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Opalg View Post
    (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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Jun 2008
    Posts
    39

    a little confused

    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??
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by duggaboy View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. factors
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: April 7th 2010, 07:26 AM
  2. Replies: 1
    Last Post: December 7th 2009, 10:42 AM
  3. sum of factors
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: June 25th 2009, 06:23 AM
  4. Factors of 2310 and Factors of 1365
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 7th 2008, 06:56 PM
  5. Factors
    Posted in the Algebra Forum
    Replies: 1
    Last Post: December 4th 2007, 04:37 AM

Search Tags


/mathhelpforum @mathhelpforum