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
    @Arturo Magidin: Many thanks for the grammar editing.2011-02-19
  • 0
    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.2011-02-19
  • 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.2011-02-19
  • 0
    (see, for example, http://planetmath.org/encyclopedia/PrimePowerDividingAFactorial.html)2011-02-19
  • 0
    @Arturo: the prime is fixed, according to his last comment.2011-02-19
  • 0
    @Arturo Magidin: Thanks! My guess based on the observation of finding the highest power of a given prime `p` in 10!. I saw my mistake, $6 = 2 * 3$.2011-02-19
  • 0
    I'm unclear which of the following two problems you are trying to solve (or if it is even something else entirely). **Problem 1.** Someone gives you a prime, say $p=7$, and an $n$, say $n=10$. Your job is to figure out the largest power of $7$ that divides $1\times 3\times 5\times\cdots\times (2(10)+1)$. **Problem 2.** Somebody gives you an $n$, say $n=6$. Your job is to first calculate $1\times 3\times 5\times\cdots\times (2(6)+1)$, then factor this number into primes, and then look at the exponents that show up in the factorization; you want to state what is the largest exponent that does.2011-02-19
  • 0
    @Chan: If your problem is "Problem 1" described above, then I have no idea why you bring up $10!$ in your question, and your formula can't possibly be correct: it will have to depend on **both** $n$ and $p$, not just $n$.2011-02-19
  • 0
    @Arturo Magidin: Problem 1 is what I meant.2011-02-19
  • 0
    @Chan: Then see Mariano's link. Your guess, as I noted above, cannot possibly be right because it does not depend on $p$; pick a $p$ larger than $2n+1$, and the answer should be $0$, but you are answering $(\lceil\frac{n}{2}\rceil -1)!$. And I still have no idea what it is you think you are doing with that $10!$.2011-02-19
  • 0
    @Arturo Magidin: The reason that I wrote down 10! because I saw it matched with all odds of the $\prod_{i=0}^{n} 2i + 1$.2011-02-19
  • 0
    @Chan: I think I'm beginning to understand; you meant that you think the highest power that divides $1\times 3\times 5\times 7\times 9$ would be the same as the highest power that divides $10!$? First: why use $10!$ and not $9!$ itself? That one already contains all the factors in your product. And, no, it won't, because an odd prime may very well divide an even number. If you look at the powers of $3$, for the number you want the answer is $3^3$, but for $10!$ (or even $9!$), it's $3^4$.2011-02-19
  • 0
    @Arturo Magidin: Thanks, I saw it what're saying. I'm trying to think of another way now :P!2011-02-19
  • 0
    @Chan: But it's not $(\lceil\frac{n}{2}\rceil - 1)!$; for your product, up to $n=4$, that would be $1!$.2011-02-19
  • 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: What a clever trick! I'm really amazed!2011-02-19
  • 0
    @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. http://mathoverflow.net/questions/26336/integer-valued-factorial-ratios2011-02-19
  • 1
    Ambikasaran: Thanks for the link. Btw, what mathoverflow is about, is that another sub branch of math.stackexchange?2011-02-19
  • 0
    @Chan: mathoverflow is mainly for people to ask and answer research level math. http://mathoverflow.net/faq. It is not related to math.stackexchange but usually there will references made across both websites.2011-02-19
  • 0
    Ambikasaran: Thank you!2011-02-20