Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

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.

share|cite|improve this answer
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).

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.