prime factorization 2

**rmpatel5** · September 15th 2008, 06:44 PM

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

**Moo** · September 16th 2008, 12:10 AM

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.

**rmpatel5** · September 16th 2008, 09:34 AM

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

**Moo** · September 16th 2008, 09:39 AM

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.

**rmpatel5** · September 16th 2008, 10:28 AM

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.

**icemanfan** · September 16th 2008, 10:59 AM

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.

**Moo** · September 16th 2008, 11:00 AM

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 ?

**rmpatel5** · September 16th 2008, 12:37 PM

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

Thread: prime factorization 2

LinkBack

Thread Tools

Display

prime factorization 2

Similar Math Help Forum Discussions

Prime Factorization

Prime factorization question

prime factorization

prime factorization

Prime Factorization Help

Search Tags