A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 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.

  • This Question is Closed
  1. Loser66
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    1 Attachment
  2. Loser66
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    @imqwerty

  3. imqwerty
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  4. imqwerty
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 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,.........}

  6. imqwerty
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  7. Loser66
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 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?

  8. imqwerty
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    yes :)

  9. Loser66
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  10. imqwerty
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  11. Loser66
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  13. Loser66
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    3 is too big, take 101, please

  14. Loser66
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    3

  18. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    Right, how did u get 3 ?

  19. Loser66
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  20. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    could you elaborate on how you got 3

  21. Loser66
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 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

  22. Loser66
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  23. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  24. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    yes,

  26. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    Try finding the "exact" count by considering few examples

  27. Loser66
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  29. Loser66
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    \(\lfloor n/p^2\rfloor\)

  30. Loser66
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  31. Loser66
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    that is 4, (2^2)

  32. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Yes

  34. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  35. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    we want to find the exponent of \(p\) in the prime factorization of \(n!\)

  36. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 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\)

  41. Loser66
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    GGGGGGGot you

  42. Loser66
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  43. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Thank you so much. I do appreciate. :)

  48. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    np :)

  49. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

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

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.