# prime factorization 2

• Sep 15th 2008, 06:44 PM
rmpatel5
prime factorization 2
a) Let http://answerboard.cramster.com/Answ...6325008366.gif with n>1, and let p be a prime number. If phttp://answerboard.cramster.com/answ...52486ce8c7.jpg 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

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 , -----,http://answerboard.cramster.com/Answ...9941595756.gifp
further , http://answerboard.cramster.com/Answ...0559756014.gifis the quotient when n is divided by p.
replacing n by n / p we get
again replacing n by n / p2 we get k(http://answerboard.cramster.com/Answ...5312053941.gif ! ) = http://answerboard.cramster.com/Answ...6020108843.gif+ k(http://answerboard.cramster.com/Answ...1137705944.gif ! )-------(3)
continuing in the same by by replacement upto http://answerboard.cramster.com/Answ...3573915740.gifwhere http://answerboard.cramster.com/Answ...1761702399.gif becomes zero, and using (2) in (1) , (3) in (2) , ---------,(n) equation in (n-1) the equation, we get
this process terminates at a finite stage while http://answerboard.cramster.com/Answ...1761702399.gif becomes for sufficiently large k .
thus, the highest power of p in n! is http://answerboard.cramster.com/Answ...3823152062.gif.

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
• Sep 16th 2008, 12:10 AM
Moo
Hello,

Quote:

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.
• Sep 16th 2008, 09:34 AM
rmpatel5
Quote:

Originally Posted by Moo
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
• Sep 16th 2008, 09:39 AM
Moo
Quote:

Originally Posted by rmpatel5
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.
• Sep 16th 2008, 10:28 AM
rmpatel5
Quote:

Originally Posted by Moo
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.
• Sep 16th 2008, 10:59 AM
icemanfan
Quote:

Originally Posted by rmpatel5
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.
• Sep 16th 2008, 11:00 AM
Moo
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 ?
• Sep 16th 2008, 12:37 PM
rmpatel5
Quote:

Originally Posted by Moo
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