# How to find the highest power of a prime $p$ that divides $\prod \limits_{i=0}^{n} 2i+1$? [duplicate]

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

-

## marked as duplicate by Marvis, Qiaochu YuanMay 5 '12 at 20:00

@Arturo Magidin: Many thanks for the grammar editing. – Chan Feb 19 '11 at 6:06
There is a well-known formula for the maximal power of a specific prime which divides a factorial number, and your products can be written as $(2n+1)!/(2^n n!)$, so you can probably deduce what you want from it. – Mariano Suárez-Alvarez Feb 19 '11 at 6:07
@Arturo Magidin: I meant the product of all odds, and a given prime p. What's the highest power of p, let say x such that $p^x$ divides that product. – Chan Feb 19 '11 at 6:08
@Arturo: the prime is fixed, according to his last comment. – Mariano Suárez-Alvarez Feb 19 '11 at 6:10

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$$

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

-
Ambikasaran: What a clever trick! I'm really amazed! – Chan Feb 19 '11 at 6:38
@Chan: Thanks, though this method is the one which is usually employed. Mariano Suárez-Alvarez mentioned it in the comment. This method is typically employed to show some ratio is an integer by proving that the power of prime dividing the ratio is non-negative. You may want to look up this MO thread. mathoverflow.net/questions/26336/… – user17762 Feb 19 '11 at 6:44
Ambikasaran: Thanks for the link. Btw, what mathoverflow is about, is that another sub branch of math.stackexchange? – Chan Feb 19 '11 at 6:49
@Chan: mathoverflow is mainly for people to ask and answer research level math. mathoverflow.net/faq. It is not related to math.stackexchange but usually there will references made across both websites. – user17762 Feb 19 '11 at 7:00
Ambikasaran: Thank you! – Chan Feb 20 '11 at 9:30