# prime factorization

Printable View

• Sep 13th 2008, 09:41 AM
rmpatel5
prime factorization
Let http://www.cramster.com/Answer-Board...6185762832.gif with n>1, and let p be a prime number. If http://www.cramster.com/Answer-Board...7486624507.gifhttp://www.cramster.com/answer-board...b34e757044.jpg n!, prove that the exponent of p in the prime factorization of n! is [n/p] + [n/p^2] + [n/p^3] +......(Note that this sum is finite, since [n/p^m]=0 if p^m>n
• Sep 13th 2008, 11:57 AM
PaulRS
Quote:

Originally Posted by rmpatel5
Let http://www.cramster.com/Answer-Board...6185762832.gif with n>1, and let p be a prime number. If http://www.cramster.com/Answer-Board...7486624507.gifhttp://www.cramster.com/answer-board...b34e757044.jpg n!, prove that the exponent of p in the prime factorization of n! is [n/p] + [n/p^2] + [n/p^3] +......(Note that this sum is finite, since [n/p^m]=0 if p^m>n

Note that in the set $\displaystyle S_n = \left\{ {1,2,...,n} \right\}$ there are $\displaystyle \left\lfloor {\tfrac{n} {p}} \right\rfloor$ multiples of $\displaystyle p$. But $\displaystyle \left\lfloor {\tfrac{n} {{p^2 }}} \right\rfloor$ of these, are multiple of $\displaystyle p^2$ and so on.

You must count once the numbers which are multiples of p but not of p², twice the numbers which are multiple of p² and not of p³,... , in order to get the maximum power of p dividing n!

And to do so it's enough to sum $\displaystyle \left\lfloor {\tfrac{n} {p}} \right\rfloor + \left\lfloor {\tfrac{n} {{p^2 }}} \right\rfloor + ...$
• Sep 13th 2008, 12:36 PM
rmpatel5
Quote:

Originally Posted by PaulRS
Note that in the set $\displaystyle S_n = \left\{ {1,2,...,n} \right\}$ there are $\displaystyle \left\lfloor {\tfrac{n} {p}} \right\rfloor$ multiples of $\displaystyle p$. But $\displaystyle \left\lfloor {\tfrac{n} {{p^2 }}} \right\rfloor$ of these, are multiple of $\displaystyle p^2$ and so on.

You must count once the numbers which are multiples of p but not of p², twice the numbers which are multiple of p² and not of p³,... , in order to get the maximum power of p dividing n!

And to do so it's enough to sum $\displaystyle \left\lfloor {\tfrac{n} {p}} \right\rfloor + \left\lfloor {\tfrac{n} {{p^2 }}} \right\rfloor + ...$

I am still lost in this proof.