Number theory question.
Please, give me a concrete example for this. I would like to understand what is going on.
 Loser66
Number theory question.
Please, give me a concrete example for this. I would like to understand what is going on.
 jamiebookeater
See more answers at brainly.com
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.
Get this expert
answer on brainly
SEE EXPERT ANSWER
Get your free account and access expert answers to this
and thousands of other questions
 Loser66
1 Attachment
 Loser66
 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
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
"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
wait sry its not n it should be p=prime :)
 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
yes :)
 Loser66
But I still not see the link between 130 and 130! :(
 imqwerty
umm u confused with that [n/m] part which i said?
 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
Take a smaller number, please, like n = 9, then n!= 3628880
 Loser66
3 is too big, take 101, please
 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
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
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
3
 ganeshie8
Right, how did u get 3 ?
 Loser66
\((9,n) \neq 1\)
 ganeshie8
could you elaborate on how you got 3
 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
oh, you want me to settle down it to multiple of 3, got it.
 ganeshie8
Okay, good. for now yes, lets just focus on numbers that are divisible by 3 only
 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
yes,
 ganeshie8
Try finding the "exact" count by considering few examples
 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
Exactly!
similarly, how many integers in that list are divisible by \(p^2\) ?
 Loser66
\(\lfloor n/p^2\rfloor\)
 Loser66
in our concrete example, it is just 1, right?
 Loser66
that is 4, (2^2)
 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
Yes
 ganeshie8
Good, save that. Lets get back to the original problem
 ganeshie8
we want to find the exponent of \(p\) in the prime factorization of \(n!\)
 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
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
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
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
\(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
GGGGGGGot you
 Loser66
Thanks for being patient to me. At the end, I got what is going on. Now, what is the elegant way?
 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
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
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
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
Thank you so much. I do appreciate. :)
 ganeshie8
np :)
Looking for something else?
Not the answer you are looking for? Search for more explanations.