## Loser66 one year ago Number theory question. Please, give me a concrete example for this. I would like to understand what is going on.

1. Loser66

2. Loser66

@imqwerty

3. imqwerty

ok so we wanna find the largest power of p which divides n! right?

4. imqwerty

so we wanna find the largest power of p contained in n! it wuld be [n/p] +[n/p^2]+[n/p^3]...... [ ] <---greatest integer function the proof of this formula can be obtained using the fact that [n/m] will give the number of integral multiples of m in n. note that this formula will wrk only if n is prime EXAMPLE- if we have- find the number of 0s at the end of 130! - SOLUTION the number of 0s at the end is equal to the exponent of 10 in 130!. now exponent of 10 (or 5x2) is equal to exponent of 5 as exponent of 2 will we lager so we find exponent of 5 in 130! [130/5]+[130/25]+[130/125]+[130/625].... 26+5+1+0+0+0.....and all will be 0 cause the denominator>numerator =32 so power of 10 =32 so no of zeros =32

5. Loser66

"note that this formula will wrk only if n is prime" , it is not true. it must be true for all n . Like if n = 300, and p is a prime 11, then the number divides 300 is $$\lfloor 300/11\rfloor = \lfloor 27.27\rfloor = 27$$ , that is {11, 22, 33, 44,55, 66,.........}

6. imqwerty

wait sry its not n it should be p=prime :)

7. Loser66

" power of 10 =32" means $$10^{32}$$ is the largest power of 10 , right? and it is found by formula [130/5] +[130/25] + [130/125]+..... right?

8. imqwerty

yes :)

9. Loser66

But I still not see the link between 130 and 130! :(

10. imqwerty

umm u confused with that [n/m] part which i said?

11. Loser66

I understand that for n = 130, then there are 26 numbers which are multiple of 5 divide 130. there are 5 numbers which are multiple of 25 divide 130 there are 1 numbers which are multiple of 125 divide 130 and sum of them is 32. But that is we are working on 130, not 130! , am I missing something?

12. Loser66

Take a smaller number, please, like n = 9, then n!= 3628880

13. Loser66

3 is too big, take 101, please

14. Loser66

Hence if n =9 , n! = 3628880 , let m =n!, prime p = 101 As the statement, $$\lfloor m/p \rfloor + \lfloor m/p^2\rfloor+\lfloor m/p^3\rfloor +\cdots = 3592+355+3+0+....+0=3950$$

15. imqwerty

XD n!=3628880 ok but we have to do it the same way it wuld be- $\left[ \frac{ 3628880 }{ 101 }\right]+\left[ \frac{ 3628880 }{ 101^2 }\right]+\left[ \frac{ 3628880 }{ 101^3 }\right].....$ =35929+355+3+0+0..=36287 suppose we want to find the power of 3 in 1200 we take 1200 in numerator part because we wanna find the number of integral multiples 1st we calculate [1200/3] =400 1200!=1200 x 1119 x 1118 x 1117........2x1 now we knw that under 1200 there are 400 numbers that are divisible by 3 when we opened 1200! those must are there in the list for example in those 400 numbers 12 and 15 must be there and 12, 15 must have appeared when we open 1200! we can write 12=3x4 adn 15=3x5 and there are 400 such numbers so 400 3s must have appeared :) and like this we calculate the multiples of 9, 27 ad so on...and add them cause the sum total of them is the number of times 3 appeared when we opened the factorial

16. ganeshie8

9! = 1*2*3*4*5*6*7*8*9 suppose we want to find the exponent of 3 in the prime factorization of 9! First, may be try answering a simpler question : How many numbers are divisible by 3 that are less than or equal to 9 ?

17. Loser66

3

18. ganeshie8

Right, how did u get 3 ?

19. Loser66

$$(9,n) \neq 1$$

20. ganeshie8

could you elaborate on how you got 3

21. Loser66

$$(9,3) =3 \neq 1$$ , hence 3 is the first one $$9,6) = 3\neq 1$$ hence 6 is the second one $$9,9) =9\neq 1$$ hence 9 is the third one therefore there are 3 numbers

22. Loser66

oh, you want me to settle down it to multiple of 3, got it.

23. ganeshie8

Okay, good. for now yes, lets just focus on numbers that are divisible by 3 only

24. ganeshie8

consider the set of integers : $$\{1, 2, 3, \ldots, n\}$$ It is easy to see that there are "approximately" $$\dfrac{n}{p}$$ integers that are divisible by $$p$$, yes ?

25. Loser66

yes,

26. ganeshie8

Try finding the "exact" count by considering few examples

27. Loser66

is it not that it is the floor of n/p. Like if n = 9 as above and p =2, then there are $$\lfloor 9/2\rfloor = 4$$ number on 9! = 1*2*3*4*5*6*7*8*9 divides 9, that is 2, 4, 6,8 which is power of 2 on 9!

28. ganeshie8

Exactly! similarly, how many integers in that list are divisible by $$p^2$$ ?

29. Loser66

$$\lfloor n/p^2\rfloor$$

30. Loser66

in our concrete example, it is just 1, right?

31. Loser66

that is 4, (2^2)

32. ganeshie8

Yes. More genereeally, can we say : There are exactly $$\left\lfloor \dfrac{n}{p^k}\right\rfloor$$ integers that are divisible by $$p^k$$ in the set of integers $$\{1, 2, 3, \ldots, n\}$$.

33. Loser66

Yes

34. ganeshie8

Good, save that. Lets get back to the original problem

35. ganeshie8

we want to find the exponent of $$p$$ in the prime factorization of $$n!$$

36. ganeshie8

One way to do it is by finding the exponent of $$p$$ in each of the factors: $$\{1,2,3,\ldots,n\}$$, then add the exponents. But we wont do it this way as there is another really nice way to count.

37. Loser66

I am very slow, please, give me the explanation for the simple way first. I can easily understand the elegant way later if I understand the easiest one, right?

38. ganeshie8

simple way is the hack way : 1) find the exponent of $$p$$ in each of the factors in $$n!$$ 2) add them up its not really interesting

39. Loser66

Like for p, and n! = 1*2*...*p*(p+1)*....*2p*(2p+1)*.....*pp (this is p^2) *(p^2+1)*....*p^3*.............................*n and then, how to turn it to the expression above.

40. ganeshie8

$$9! = 1*2*3*4*5*6*7*8*9$$ to find the exponent of $$3$$ in the prime factorization of $$9!$$ : 1) exponent of 3 in 1 = 0, exponent of 3 in 2 = 0, exponent of 3 in 3 = 1, exponent of 3 in 4 = 0, exponent of 3 in 5 = 0, exponent of 3 in 6 = 1, exponent of 3 in 7 = 0, exponent of 3 in 8 = 0, exponent of 3 in 9 = 2, 2) add the exponents : 0 + 0 + 1 + 0 + 0 + 1 + 0 + 0 + 2 = $$4$$

41. Loser66

GGGGGGGot you

42. Loser66

Thanks for being patient to me. At the end, I got what is going on. Now, what is the elegant way?

43. ganeshie8

We have observed earlier that there are exactly $$\left\lfloor \dfrac{n}{p}\right\rfloor$$ divisors of $$p$$ in the set of integers : $$\{1,2,3,\ldots, n\}$$. These give one power of $$p$$.

44. ganeshie8

there are exactly $$\left\lfloor \dfrac{n}{p^2}\right\rfloor$$ divisors of $$p^2$$ in the set of integers : $$\{1,2,3,\ldots, n\}$$. These give another power of $$p$$.

45. ganeshie8

there are exactly $$\left\lfloor \dfrac{n}{p^3}\right\rfloor$$ divisors of $$p^3$$ in the set of integers : $$\{1,2,3,\ldots, n\}$$. These give yet another power of $$p$$.

46. ganeshie8

Continuine to infinity : exponent of $$p$$ in the prime factorization of $$n!$$ is given by $$\sum\limits_{k=1}^{\infty} \left\lfloor \dfrac{n}{p^k}\right\rfloor$$

47. Loser66

Thank you so much. I do appreciate. :)

48. ganeshie8

np :)