Determine whether $\frac{1000!}{100!^{10}}$ is an integer

Question

Can you give an idea, how to find out whether the result of ${1000!}/{100!^{10}}$ an integer.

Modulo division? But what I met was about powers like $2^{100}/125$...

Answer 1

What's the number of ways to split $1000$ people into $10$ teams of $100$ ?

Answer 2

Since you tagged this abstract algebra, I will give a hint based on it: the group $$\underbrace{S_{100}\times\cdots\times S_{100}}_{10\text{ copies}}$$ has an obvious embedding as a subgroup of $S_{1000}$.

Answer 3

Consider the binomial coefficents ${200 \choose 100},{300 \choose 100},{400 \choose 100},{500 \choose 100},{600 \choose 100},{700 \choose 100},{800 \choose 100},{900 \choose 100},{1000 \choose 100}$

For example,

$${700 \choose 100} = \frac{700!}{600!100!} = \frac{700\cdot 699\ldots 602\cdot 601}{100!}$$ and this is an integer...

Answer 4

Here’s a non-combinatorial, more number-theoretic proof. For any prime $p$ the number of factors of $p$ in $n!$ is

$$\sum_{k\ge 0}\left\lfloor\frac{n!}{p^k}\right\rfloor\;,$$

so it suffices to show for an arbitrary prime $p$ that

$$10\sum_{k\ge 0}\left\lfloor\frac{100}{p^k}\right\rfloor\le\sum_{k\ge 0}\left\lfloor\frac{1000}{p^k}\right\rfloor\;.\tag{1}$$

$(1)$ will certainly be true if

$$10\left\lfloor\frac{100}{p^k}\right\rfloor\le\left\lfloor\frac{1000}{p^k}\right\rfloor\tag{2}$$

for primes $p$ and $k\ge 0$. But

$$\left\lfloor\frac{100}{p^k}\right\rfloor\le\frac{100}{p^k}\;,$$

so

$$10\left\lfloor\frac{100}{p^k}\right\rfloor\le\frac{1000}{p^k}\;,$$

and $(2)$ (and hence $(1)$) follows immediately.

Answer 5

The basic result is that the product of $k$ consecutive numbers is divisible by $k!$.

This is the fact that ${{n}\choose{k}}$ is an integer when $n \ge k$.

Now, $1000!$ can be decomposed into $10$ products of $100$ consecutive numbers.

Answer 6

I have a stronger statement:

$$\binom{1000}{100}=\frac{1000!}{100!^{10}\binom{900}{100}\binom{800}{100}\binom{700}{100}\binom{600}{100}\binom{500}{100}\binom{400}{100}\binom{300}{100}\binom{200}{100}}$$

is an integer. More generally:

$$\binom{ab}{b}=\frac{(ab)!}{b!^{a}\binom{(a-1)b}{b}\binom{(a-2)b}{b}\cdots\binom{2b}{b}}$$

is an integer (for $a\ge 2, b\ge 0$).