# Thread: prime factorization 2

1. ## 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

2. 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.

3. 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

4. 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.

5. 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.

6. 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.

7. 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 ?

8. 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