6
$\begingroup$

Possible Duplicate:
How come the number $N!$ can terminate in exactly $1,2,3,4,$ or $6$ zeroes but never $5$ zeroes?

Given an odd prime $p$, how does one find the highest power of $p$ that divides $\displaystyle\prod_{i=0}^n(2i+1)?$

I wrote it down all paper and realized that the highest power of $p$ that divides this product will be the same as the highest power of $p$ that divides $(\lceil\frac{n}{2}\rceil - 1)!$

Since $10! = 1\times 2\times 3\times 4\times 5\times 6\times 7\times 8\times 9\times 10$ while $\prod_{i=0}^{4} (2i+1) = 1\times 3\times 5\times 7\times 9$

Am I in the right track?

Thanks,
Chan

  • 0
    The product you are describing is often denoted by the double factorial, as 9!! for your example2011-02-19

1 Answers 1

9

Note that $\displaystyle \prod_{i=1}^{n} (2i-1) = \frac{(2n)!}{2^n n!}$.

Clearly, the highest power of $2$ dividing the above product is $0$.

For odd primes $p$, we proceed as follows.

Note that the highest power of $p$ dividing $\frac{a}{b}$ is nothing but the highest power of $p$ dividing $a$ - highest power of $p$ dividing $b$.

i.e. if $s_p$ is the highest power of $p$ dividing $\frac{a}{b}$ and $s_{p_a}$ is the highest power of $p$ dividing $a$ and $s_{p_b}$ is the highest power of $p$ dividing $b$, then $s_p = s_{p_a}-s_{p_b}$.

So the highest power of $p$ dividing $\displaystyle \frac{(2n)!}{2^n n!}$ is nothing but $s_{(2n)!}-s_{2^n}-s_{n!}$.

Note that $s_{2^n} = 0$.

Now if you want to find the maximum power of a prime $q$ dividing $N!$, it is given by $s_{N!} = \left \lfloor \frac{N}{q} \right \rfloor + \left \lfloor \frac{N}{q^2} \right \rfloor + \left \lfloor \frac{N}{q^3} \right \rfloor + \cdots$

(Look up this stackexchange thread for the justification of the above claim)

Hence, the highest power of a odd prime $p$ dividing the product is $\left ( \left \lfloor \frac{2N}{p} \right \rfloor + \left \lfloor \frac{2N}{p^2} \right \rfloor + \left \lfloor \frac{2N}{p^3} \right \rfloor + \cdots \right ) - \left (\left \lfloor \frac{N}{p} \right \rfloor + \left \lfloor \frac{N}{p^2} \right \rfloor + \left \lfloor \frac{N}{p^3} \right \rfloor + \cdots \right)$

  • 0
    Ambikasaran: Thank you!2011-02-20