Results 1 to 8 of 8

Math Help - prime factorization 2

  1. #1
    Junior Member
    Joined
    Sep 2008
    Posts
    62

    prime factorization 2

    a) Let with n>1, and let p be a prime number. If p 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

    my answer to part a)
    this can also be said as the highest power of a prime number p contained in n !.
    given p divides n !.
    so, let k( n ! ) be the highest power of p contained in n ! .
    then the multiples of p which are the divisors of n ! are p , 2p , 3p , -----,p
    further , is the quotient when n is divided by p.
    so, k ( n!) = +k( ! ) -------------(1)
    replacing n by n / p we get
    k( ! ) = +k( ! ) -----------(2)
    again replacing n by n / p2 we get k( ! ) = + k( ! )-------(3)
    continuing in the same by by replacement upto where becomes zero, and using (2) in (1) , (3) in (2) , ---------,(n) equation in (n-1) the equation, we get
    k( n !) =
    this process terminates at a finite stage while becomes for sufficiently large k .
    thus, the highest power of p in n! is .

    b) Use (part a) above to find the prime factorization of 20!

    c) Find the number of zeros with each the decimal representaion of 100! terminates
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,

    b) Use (part a) above to find the prime factorization of 20!
    20!=20 \times 19 \times 18 \times \dots \times 1

    The prime numbers < 20 are 2,3,5,7,11,13,17,19
    So apply the formula for all of these, so that you get their highest power in 20! And this gives the prime factorisation of 20!

    c) one zero at the end = 1 factor 10. 10=2x5. So see what's the power of 5 in the prime factorisation of 100! also find the power of 2, though the latter is not useful since one can see that there are much more factors 2 than 5.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Sep 2008
    Posts
    62
    Quote Originally Posted by Moo View Post
    Hello,



    20!=20 \times 19 \times 18 \times \dots \times 1

    The prime numbers < 20 are 2,3,5,7,11,13,17,19
    So apply the formula for all of these, so that you get their highest power in 20! And this gives the prime factorisation of 20!

    c) one zero at the end = 1 factor 10. 10=2x5. So see what's the power of 5 in the prime factorisation of 100! also find the power of 2, though the latter is not useful since one can see that there are much more factors 2 than 5.
    For part b do i plug it into [n/p] + [n/p^2] + [n/p^3]. If so, would it go like this; 20/2 + 20/3^2 + 20/5^3...and so on. If that is the case this does not get to the product of 20!

    For part c I am just soo lost. I know the answer is suppose to be 24 but have no clue what is going on
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Quote Originally Posted by rmpatel5 View Post
    For part b do i plug it into [n/p] + [n/p^2] + [n/p^3]. If so, would it go like this; 20/2 + 20/3^2 + 20/5^3...and so on. If that is the case this does not get to the product of 20!

    For part c I am just soo lost. I know the answer is suppose to be 24 but have no clue what is going on
    No !

    Let 20!=\prod_{i=1}^{p} p_i^{\alpha_i}

    Formula : \alpha_i=[20/p_i]+[20/p_i^2]+\dots

    Since [ ] is the least integer function, there is a moment where the terms will be equal to 0.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Sep 2008
    Posts
    62
    Quote Originally Posted by Moo View Post
    No !

    Let 20!=\prod_{i=1}^{p} p_i^{\alpha_i}

    Formula : \alpha_i=[20/p_i]+[20/p_i^2]+\dots

    Since [ ] is the least integer function, there is a moment where the terms will be equal to 0.
    Does it go something like this:

    20!=2^20/2 * 3^(20/3 + 20/9) * 5^(20/5 + 20/5^2 + 20/5^3) * 7^(20/7+ 20/7^2+20/7^3+20/7^4)*.......till 19.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Apr 2008
    Posts
    1,092
    Quote Originally Posted by rmpatel5 View Post
    Does it go something like this:

    20!=2^20/2 * 3^(20/3 + 20/9) * 5^(20/5 + 20/5^2 + 20/5^3) * 7^(20/7+ 20/7^2+20/7^3+20/7^4)*.......till 19.
    Something like that. You keep going on one prime number until the next term would be equal to zero. So that makes your first term 2^([20/2] + [20/4] + [20/8] + [20/16]), your second term 3^([20/3] + [20/9]), your third term 5^([20/5]), and so on.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    I hate doing it, but I think I'll have to show you some examples as to how to do.

    \lfloor x \rfloor=\max ~\{n \in \mathbb{N} / n \le x\}= \text{ the greatest integer smaller than x }

    For example \lfloor 3.548787 \rfloor=3
    \lfloor 0.54878 \rfloor=0

    -----------------------------------
    Question : what is the power of p_1=2, \alpha_1, in the prime factorisation of 20 ?

    The formula tells us it is :
    \alpha_1=\lfloor \tfrac{20}{2} \rfloor+\lfloor \tfrac{20}{2^2} \rfloor+\lfloor \tfrac{20}{2^3} \rfloor+\lfloor \tfrac{20}{2^4} \rfloor+\lfloor \tfrac{20}{2^5} \rfloor+\dots

    \alpha_1=\lfloor 10 \rfloor+\lfloor 5 \rfloor+\lfloor 2.5 \rfloor+\lfloor 1.25 \rfloor+\lfloor 0.625 \rfloor+\dots

    \alpha_1=10+5+2+1+0+\dots

    What will follow after the 0 are 0's too because you keep dividing 20 by a large number. And as soon as it becomes less than 1, the value \lfloor x \rfloor becomes 0.

    Thus \alpha_1=18 \implies 2^{18} \text{ is a factor of } 20!


    Question : what is the power of p_3=5, \alpha_3 in the prime factorisation of 20! ?

    \alpha_3=\lfloor \tfrac{20}{5} \rfloor+\lfloor \tfrac{20}{5^2} \rfloor+\lfloor \tfrac{20}{5^3} \rfloor+\dots

    \alpha_3=\lfloor 4 \rfloor+\lfloor 0.8 \rfloor+\lfloor 0.16 \rfloor+\dots

    \alpha_3=4+0+0+\dots=4

    Thus 5^4 divides 20!




    Do it for all prime numbers, labelled from 1 to ... m

    20!=p_1^{\alpha_1} \times p_2^{\alpha_2} \times p_3^{\alpha_3} \times \dots \times p_m^{\alpha_m}=\prod_{i=1}^m p_i^{\alpha_i}


    Got it ?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Sep 2008
    Posts
    62
    Quote Originally Posted by Moo View Post
    I hate doing it, but I think I'll have to show you some examples as to how to do.

    \lfloor x \rfloor=\max ~\{n \in \mathbb{N} / n \le x\}= \text{ the greatest integer smaller than x }

    For example \lfloor 3.548787 \rfloor=3
    \lfloor 0.54878 \rfloor=0

    -----------------------------------
    Question : what is the power of p_1=2, \alpha_1, in the prime factorisation of 20 ?

    The formula tells us it is :
    \alpha_1=\lfloor \tfrac{20}{2} \rfloor+\lfloor \tfrac{20}{2^2} \rfloor+\lfloor \tfrac{20}{2^3} \rfloor+\lfloor \tfrac{20}{2^4} \rfloor+\lfloor \tfrac{20}{2^5} \rfloor+\dots

    \alpha_1=\lfloor 10 \rfloor+\lfloor 5 \rfloor+\lfloor 2.5 \rfloor+\lfloor 1.25 \rfloor+\lfloor 0.625 \rfloor+\dots

    \alpha_1=10+5+2+1+0+\dots

    What will follow after the 0 are 0's too because you keep dividing 20 by a large number. And as soon as it becomes less than 1, the value \lfloor x \rfloor becomes 0.

    Thus \alpha_1=18 \implies 2^{18} \text{ is a factor of } 20!


    Question : what is the power of p_3=5, \alpha_3 in the prime factorisation of 20! ?

    \alpha_3=\lfloor \tfrac{20}{5} \rfloor+\lfloor \tfrac{20}{5^2} \rfloor+\lfloor \tfrac{20}{5^3} \rfloor+\dots

    \alpha_3=\lfloor 4 \rfloor+\lfloor 0.8 \rfloor+\lfloor 0.16 \rfloor+\dots

    \alpha_3=4+0+0+\dots=4

    Thus 5^4 divides 20!




    Do it for all prime numbers, labelled from 1 to ... m

    20!=p_1^{\alpha_1} \times p_2^{\alpha_2} \times p_3^{\alpha_3} \times \dots \times p_m^{\alpha_m}=\prod_{i=1}^m p_i^{\alpha_i}


    Got it ?
    You the man MOOO COW!!! Makes soo much more sense
    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
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 13th 2008, 12:36 PM
  5. prime factorization
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 18th 2008, 06:51 PM

Search Tags


/mathhelpforum @mathhelpforum