# What is the highest power of a prime that divides nPr?

I know that the highest power of a prime which divides $n!$ is given by $$\left[\frac np\right]+\left[\frac n{p^2}\right]+\left[\frac n{p^3}\right]...$$ Where $[x]$ is the greatest integer function.

For $^{n}P_{r}$, which equals $\frac{n!}{(n-r)!}$, I can find the highest power of $p$ dividing $n!$ and $(n-r)!$, and then subtract the two to get the highest power of $p$ dividing $^{n}P_{r}$.

Now is there a better method to do this, where we don't need to find the highest power of $p$ dividing $(n-r)!$? Can we directly find the power of $p$ dividing the product of $r$ consecutive integers?

-

No, because it depends on which $r$ consecutive integers you take (for example, if one of them is $p^{1000}$ you might get a fairly high power). The way to think about computing the $p$-adic valuation of $\binom{n}{r}$ (the first is a fancy name for what you are computing, the second a FAR better notation for your $P$) is this:

Write $r$ and $n-r$ in base $p,$ and then count how many carries you have when adding them.

-
I don't understand how this works? –  udiboy1209 Dec 13 '13 at 3:52
... of $n\choose r$? I think adiboy is asking for $P(n,r)$. –  Doc Dec 13 '13 at 3:53

The largest power of $p$ which divides $n!$ is the number of times $p$ appears in the factorization of $n!$. This is the same as finding how many times $p$ appears in the factorization of $n,n-1,n-2,\cdots,2,1$.

Now using the division algorithm, given an $a \in \mathbb{Z}$, we can find a $q$ and $r$ such that $a=qp+r$, where $0\leq r <p$. Then we have $a/p=q+r/p$. Then taking the greatest integer function of both sides yields $$\lfloor a/p\rfloor = \lfloor q\rfloor +\lfloor r/p\rfloor=q+0=q$$ Of course, $p^2$ may divide one or more of $n,n-1,n-2,\cdots,2,1$, say $i$. Then we can use the same idea as before. So let $n(x,p)$ be the largest power of $p$ that divides $x!$. Then $$n(x,p)=\sum_{k \in \mathbb{Z}_+}\sum_{j=1}^x \left\lfloor \frac{x}{p^k} \right\rfloor$$ Of course, this sum converges as the floor function is $0$ for sufficiently large $k$. In general, this is about as good as a method as one gets without sufficiently advanced methods (that often only lengthen the issue).

-