# Thread: Number Theory Help Part 2

1. ## Number Theory Help Part 2

exp(p, n!) = \sum_{i=1}^{\infty} \lfloor \frac{n}{p^i}\rfloor

After getting the first formula above, please help me build the more general formula for the exponent of any particular prime in the prime factorization of the product of any set of
consecutive positive integers (which can be expressed as nPr ).

For the purposes of this problem, we introduce the notation

exp(p, nPr)= the exponent of prime p in the PF of nPr

Example: exp(5, 25P6)=3

2. ## One step further

$\displaystyle exp(p, n!) = \sum_{i=1}^{\infty} \lfloor \frac{n}{p^i}\rfloor$

$\displaystyle _nP_r=\frac{n!}{(n-r)!}$

So $\displaystyle exp(p, nPr) = exp(p,n) - exp(p, n-r)$

$\displaystyle exp(p, nPr) = \sum_{i=1}^{\infty} \lfloor \frac{n}{p^i}\rfloor - \lfloor \frac{n-r}{p^i}\rfloor$

$\displaystyle exp(p, nPr) \approx \sum_{i=1}^{\infty} \frac{r}{p^i}$

I don't think there's an explicit way to simplify the sum of two floor functions, so the error term on this approximation will be $\displaystyle \pm \lfloor \frac{\ln n}{\ln p}\rfloor$ . Just like in the original, you don't have to sum to $\displaystyle \infty$, only to $\displaystyle \lfloor \frac{\ln n}{\ln p}\rfloor$ .

3. ## Last Part Help

Prove that a number of the form nCr (where n is an integer and is greater than or equal to r) must be a positive integer.

Thanks.

4. ## Not a fraction

Prove that a number of the form $\displaystyle \frac{n!}{(n-r)!r!}$ comes out to a whole number, not a fraction, as long as $\displaystyle n>r$ and both are positive integers. They are asking you to prove that everything without exception in the denominator cancels with something in the numerator.

5. Oh I understand the question now, but how are you supposed to get from the first two things that you solved for to this step?

I actually tried to do a proof by contradiction, because as you substitute the values found in the first 2 (you have to prove the numerator is greater than the denominator), but it's not complete- any help?

6. ## Hint to get you started

Here's a hint that makes things simpler: Start by proving $\displaystyle \frac{n!}{(n-r)!}$ is always a whole number, and call it P.

Then show why $\displaystyle \frac P{r!}$ would always be a whole number...