2
$\begingroup$

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?

$\endgroup$

2 Answers 2

1
$\begingroup$

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.

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

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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