A community for students.
Here's the question you clicked on:
 0 viewing
Loser66
 one year ago
Number theory question.
Please, give me a concrete example for this. I would like to understand what is going on.
Loser66
 one year ago
Number theory question. Please, give me a concrete example for this. I would like to understand what is going on.

This Question is Closed

imqwerty
 one year ago
Best ResponseYou've already chosen the best response.1ok so we wanna find the largest power of p which divides n! right?

imqwerty
 one year ago
Best ResponseYou've already chosen the best response.1so 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

Loser66
 one year ago
Best ResponseYou've already chosen the best response.0"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,.........}

imqwerty
 one year ago
Best ResponseYou've already chosen the best response.1wait sry its not n it should be p=prime :)

Loser66
 one year ago
Best ResponseYou've already chosen the best response.0" 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?

Loser66
 one year ago
Best ResponseYou've already chosen the best response.0But I still not see the link between 130 and 130! :(

imqwerty
 one year ago
Best ResponseYou've already chosen the best response.1umm u confused with that [n/m] part which i said?

Loser66
 one year ago
Best ResponseYou've already chosen the best response.0I 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?

Loser66
 one year ago
Best ResponseYou've already chosen the best response.0Take a smaller number, please, like n = 9, then n!= 3628880

Loser66
 one year ago
Best ResponseYou've already chosen the best response.03 is too big, take 101, please

Loser66
 one year ago
Best ResponseYou've already chosen the best response.0Hence 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\)

imqwerty
 one year ago
Best ResponseYou've already chosen the best response.1XD 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

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.29! = 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 ?

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2Right, how did u get 3 ?

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2could you elaborate on how you got 3

Loser66
 one year ago
Best ResponseYou've already chosen the best response.0\((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

Loser66
 one year ago
Best ResponseYou've already chosen the best response.0oh, you want me to settle down it to multiple of 3, got it.

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2Okay, good. for now yes, lets just focus on numbers that are divisible by 3 only

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2consider 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 ?

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2Try finding the "exact" count by considering few examples

Loser66
 one year ago
Best ResponseYou've already chosen the best response.0is 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!

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2Exactly! similarly, how many integers in that list are divisible by \(p^2\) ?

Loser66
 one year ago
Best ResponseYou've already chosen the best response.0\(\lfloor n/p^2\rfloor\)

Loser66
 one year ago
Best ResponseYou've already chosen the best response.0in our concrete example, it is just 1, right?

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2Yes. 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\}\).

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2Good, save that. Lets get back to the original problem

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2we want to find the exponent of \(p\) in the prime factorization of \(n!\)

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2One 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.

Loser66
 one year ago
Best ResponseYou've already chosen the best response.0I 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?

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2simple 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

Loser66
 one year ago
Best ResponseYou've already chosen the best response.0Like 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.

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2\(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\)

Loser66
 one year ago
Best ResponseYou've already chosen the best response.0Thanks for being patient to me. At the end, I got what is going on. Now, what is the elegant way?

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2We 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\).

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2there 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\).

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2there 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\).

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2Continuine 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\)

Loser66
 one year ago
Best ResponseYou've already chosen the best response.0Thank you so much. I do appreciate. :)
Ask your own question
Sign UpFind more explanations on OpenStudy
Your question is ready. Sign up for free to start getting answers.
spraguer
(Moderator)
5
→ View Detailed Profile
is replying to Can someone tell me what button the professor is hitting...
23
 Teamwork 19 Teammate
 Problem Solving 19 Hero
 Engagement 19 Mad Hatter
 You have blocked this person.
 ✔ You're a fan Checking fan status...
Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.