Results 1 to 3 of 3

Thread: 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 $\displaystyle
    S_n = \left\{ {1,2,...,n} \right\}
    $ there are $\displaystyle
    \left\lfloor {\tfrac{n}
    {p}} \right\rfloor
    $ multiples of $\displaystyle p$. But $\displaystyle
    \left\lfloor {\tfrac{n}
    {{p^2 }}} \right\rfloor
    $ of these, are multiple of $\displaystyle
    p^2
    $ 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 $\displaystyle
    \left\lfloor {\tfrac{n}
    {p}} \right\rfloor + \left\lfloor {\tfrac{n}
    {{p^2 }}} \right\rfloor + ...
    $
    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 $\displaystyle
    S_n = \left\{ {1,2,...,n} \right\}
    $ there are $\displaystyle
    \left\lfloor {\tfrac{n}
    {p}} \right\rfloor
    $ multiples of $\displaystyle p$. But $\displaystyle
    \left\lfloor {\tfrac{n}
    {{p^2 }}} \right\rfloor
    $ of these, are multiple of $\displaystyle
    p^2
    $ 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 $\displaystyle
    \left\lfloor {\tfrac{n}
    {p}} \right\rfloor + \left\lfloor {\tfrac{n}
    {{p^2 }}} \right\rfloor + ...
    $
    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: Mar 23rd 2014, 11:02 AM
  2. Prime Factorization
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: Sep 21st 2010, 02:56 PM
  3. Prime factorization question
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Nov 9th 2009, 11:16 AM
  4. prime factorization 2
    Posted in the Algebra Forum
    Replies: 7
    Last Post: Sep 16th 2008, 12:37 PM
  5. prime factorization
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Feb 18th 2008, 06:51 PM

Search Tags


/mathhelpforum @mathhelpforum