Find the greatest power of $104$ which divides $10000!$

Question

Find the greatest power of $104$ which divides $10000!$

I thought $$104=2^3\cdot13$$ so I have to find $n$ such that $$(2^3\cdot13)^n\mid 10000!$$ Obviously, we can see that there are fewer factors $13$ than $2$, then to solve this, we need to find the largest power of $13$ that divides $10000!$

$$E_{13}(10000!)=\left[\frac{10000}{13} \right]+\left[\frac{10000}{13^2} \right]+\left[\frac{10000}{13^3} \right]=769+59+4=832$$ As $13^4>10000$ then stopped at $13^3$.

$\fbox{Therefore, the higher power 104 that divides 10000! is 832}$

Is this correct? Because I can say that there are two more factors than thirteen?

Answer 1

I didn't check your calculation, but this is right. If you want a proof, just write down the same sum with $8$ replacing $13$; this is a gross underestimate for how many times $8$ divides $13!$ since it ignores even numbers that aren't multiples of $8$, but it is still greater than the sum you wrote down (without even calculating, since it is term for term greater and there are more terms in it).

Answer 2

The number of times a prime divides a given factorial, might be derived thus (example is 13)

For 10000!, there are 769 multiples of 13, each producing a prime 13, and a number whose product is 769!. (ie there's 13*1, 13*2, ..., 13*769).

For 769!, there are 59 multiples of 13, and 59! is what you get when you divide the product of these multiples of 13.

and so forth, to 59! and then 4!.

When one uses a power of 13, say 2197 (or 1.0.0.0 base 13), there are 1.0.0 multiples of 13, and 1.0 multiples of 169, and 1 multiple of 2197. Since every digit in every place follows this rule, one finds that 1.1.1 = (1.0.0.0 - 1)/12 etc.

One can then find the number of 13's in a number, if one knows the digits of the number in base 13: ie 10000 = 4,7,2,3. These numbers add to 4+7+2+3 = 16, and 10000-16 = 12* = 832.

Since one expects then a divisor of p on average once every (p-1), it is fairly easy to work out the dominate prime(s) to look at.

For 104, we have 2 (which produces on average, one every place, but 8 requires 3 places), and 13 (one every 12 places), so we only need to check for 13.

For something like 720 or 12, we expect this number every 4 or 2 places, but we have to check every prime, since 2^4, 3^2, 5^1 each would appear once every four places.