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

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

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

1
@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
– Mariano Suárez-Alvarez♦ Feb 19 '11 at 6:09
@Arturo: the prime is fixed, according to his last comment. – Mariano Suárez-Alvarez♦ Feb 19 '11 at 6:10
show 10 more comments

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

## 1 Answer

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

-
Ambikasaran: What a clever trick! I'm really amazed! – Chan Feb 19 '11 at 6:38
– user17762 Feb 19 '11 at 6:44

1
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
– user17762 Feb 19 '11 at 7:00
Ambikasaran: Thank you! – Chan Feb 20 '11 at 9:30
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 40, "mathjax_display_tex": 5, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9166158437728882, "perplexity_flag": "head"}