Loser66
  • Loser66
Number theory question. Please, give me a concrete example for this. I would like to understand what is going on.
Mathematics
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
schrodinger
  • schrodinger
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
Loser66
  • Loser66
1 Attachment
Loser66
  • Loser66
@imqwerty
imqwerty
  • imqwerty
ok so we wanna find the largest power of p which divides n! right?

Looking for something else?

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

More answers

imqwerty
  • 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
Loser66
  • 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,.........}
imqwerty
  • imqwerty
wait sry its not n it should be p=prime :)
Loser66
  • 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?
imqwerty
  • imqwerty
yes :)
Loser66
  • Loser66
But I still not see the link between 130 and 130! :(
imqwerty
  • imqwerty
umm u confused with that [n/m] part which i said?
Loser66
  • 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?
Loser66
  • Loser66
Take a smaller number, please, like n = 9, then n!= 3628880
Loser66
  • Loser66
3 is too big, take 101, please
Loser66
  • 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\)
imqwerty
  • 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
ganeshie8
  • 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 ?
Loser66
  • Loser66
3
ganeshie8
  • ganeshie8
Right, how did u get 3 ?
Loser66
  • Loser66
\((9,n) \neq 1\)
ganeshie8
  • ganeshie8
could you elaborate on how you got 3
Loser66
  • 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
Loser66
  • Loser66
oh, you want me to settle down it to multiple of 3, got it.
ganeshie8
  • ganeshie8
Okay, good. for now yes, lets just focus on numbers that are divisible by 3 only
ganeshie8
  • 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 ?
Loser66
  • Loser66
yes,
ganeshie8
  • ganeshie8
Try finding the "exact" count by considering few examples
Loser66
  • 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!
ganeshie8
  • ganeshie8
Exactly! similarly, how many integers in that list are divisible by \(p^2\) ?
Loser66
  • Loser66
\(\lfloor n/p^2\rfloor\)
Loser66
  • Loser66
in our concrete example, it is just 1, right?
Loser66
  • Loser66
that is 4, (2^2)
ganeshie8
  • 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\}\).
Loser66
  • Loser66
Yes
ganeshie8
  • ganeshie8
Good, save that. Lets get back to the original problem
ganeshie8
  • ganeshie8
we want to find the exponent of \(p\) in the prime factorization of \(n!\)
ganeshie8
  • 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.
Loser66
  • 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?
ganeshie8
  • 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
Loser66
  • 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.
ganeshie8
  • 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\)
Loser66
  • Loser66
GGGGGGGot you
Loser66
  • Loser66
Thanks for being patient to me. At the end, I got what is going on. Now, what is the elegant way?
ganeshie8
  • 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\).
ganeshie8
  • 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\).
ganeshie8
  • 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\).
ganeshie8
  • 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\)
Loser66
  • Loser66
Thank you so much. I do appreciate. :)
ganeshie8
  • ganeshie8
np :)

Looking for something else?

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