Results 1 to 3 of 3

Math Help - prime factorization

  1. #1
    Junior Member
    Joined
    Sep 2008
    Posts
    62

    prime factorization

    Let with n>1, and let p be a prime number. If n!, prove that the exponent of p in the prime factorization of n! is [n/p] + [n/p^2] + [n/p^3] +......(Note that this sum is finite, since [n/p^m]=0 if p^m>n
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Quote Originally Posted by rmpatel5 View Post
    Let with n>1, and let p be a prime number. If n!, prove that the exponent of p in the prime factorization of n! is [n/p] + [n/p^2] + [n/p^3] +......(Note that this sum is finite, since [n/p^m]=0 if p^m>n
    Note that in the set <br />
S_n  = \left\{ {1,2,...,n} \right\}<br />
there are <br />
\left\lfloor {\tfrac{n}<br />
{p}} \right\rfloor <br />
multiples of p. But <br />
\left\lfloor {\tfrac{n}<br />
{{p^2 }}} \right\rfloor <br />
of these, are multiple of <br />
p^2 <br />
and so on.

    You must count once the numbers which are multiples of p but not of p, twice the numbers which are multiple of p and not of p,... , in order to get the maximum power of p dividing n!

    And to do so it's enough to sum <br />
\left\lfloor {\tfrac{n}<br />
{p}} \right\rfloor  + \left\lfloor {\tfrac{n}<br />
{{p^2 }}} \right\rfloor  + ...<br />
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Sep 2008
    Posts
    62
    Quote Originally Posted by PaulRS View Post
    Note that in the set <br />
S_n  = \left\{ {1,2,...,n} \right\}<br />
there are <br />
\left\lfloor {\tfrac{n}<br />
{p}} \right\rfloor <br />
multiples of p. But <br />
\left\lfloor {\tfrac{n}<br />
{{p^2 }}} \right\rfloor <br />
of these, are multiple of <br />
p^2 <br />
and so on.

    You must count once the numbers which are multiples of p but not of p, twice the numbers which are multiple of p and not of p,... , in order to get the maximum power of p dividing n!

    And to do so it's enough to sum <br />
\left\lfloor {\tfrac{n}<br />
{p}} \right\rfloor  + \left\lfloor {\tfrac{n}<br />
{{p^2 }}} \right\rfloor  + ...<br />
    I am still lost in this proof.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prime Factorization Help
    Posted in the Algebra Forum
    Replies: 11
    Last Post: March 23rd 2014, 11:02 AM
  2. Prime Factorization
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: September 21st 2010, 02:56 PM
  3. Prime factorization question
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 9th 2009, 11:16 AM
  4. prime factorization 2
    Posted in the Algebra Forum
    Replies: 7
    Last Post: September 16th 2008, 12:37 PM
  5. prime factorization
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 18th 2008, 06:51 PM

Search Tags


/mathhelpforum @mathhelpforum