求证：当n为自然数时，$(n!)^n \mid (n^2)!$（纯变量推导）

Let's work through proving this divisibility result step by step—we'll use Legendre's Formula, which is perfect for comparing prime exponents in factorials, the core of any divisibility proof involving factorials.

Background: Legendre's Formula #

For any prime $p$ and positive integer $m$, the exponent of $p$ in the prime factorization of $m!$ (written as $v_p(m!)$) is calculated by:
$$v_p(m!) = \sum_{k=1}^{\infty} \left\lfloor \frac{m}{p^k} \right\rfloor$$
Here, $\lfloor x \rfloor$ is the floor function—it returns the greatest integer less than or equal to $x$.

To show $(n!)^n \mid (n^2)!$, we just need to verify that for every prime $p$, the exponent of $p$ in $(n^2)!$ is at least $n$ times the exponent of $p$ in $n!$. In mathematical terms:
$$v_p((n^2)!) \geq n \cdot v_p(n!)$$

Step-by-Step Derivation #

1. Expand both sides with Legendre's Formula

   • Left-hand side (LHS): $v_p((n^2)!) = \sum_{k=1}^{\infty} \left\lfloor \frac{n^2}{pk} \right\rfloor$
   • Right-hand side (RHS): $n \cdot v_p(n!) = n \cdot \sum_{k=1}^{\infty} \left\lfloor \frac{n}{p^k} \right\rfloor = \sum_{k=1}^{\infty} n \left\lfloor \frac{n}{p^k} \right\rfloor$

2. Prove the inequality for each term in the sum
   Pick any fixed $k \geq 1$, and let $q = \left\lfloor \frac{n}{p^k} \right\rfloor$. By the definition of the floor function:
   $$q \leq \frac{n}{p^k} < q + 1$$
   Multiply all parts of this inequality by $n$:
   $$nq \leq \frac{n^2}{pk} < n(q + 1)$$
   Since $\lfloor x \rfloor$ is the largest integer not exceeding $x$, we know $\left\lfloor \frac{n^2}{pk} \right\rfloor \geq nq$ (because $\frac{n^2}{pk}$ is at least $nq$, and $nq$ is an integer). Substitute back $q = \left\lfloor \frac{n}{p^k} \right\rfloor$, and we get:
   $$\left\lfloor \frac{n^2}{pk} \right\rfloor \geq n \left\lfloor \frac{n}{p^k} \right\rfloor$$

3. Sum the inequalities across all $k$
   Adding the above inequality for every $k \geq 1$ gives us:
   $$\sum_{k=1}^{\infty} \left\lfloor \frac{n^2}{pk} \right\rfloor \geq \sum_{k=1}^{\infty} n \left\lfloor \frac{n}{p^k} \right\rfloor$$
   Which simplifies directly to our required condition:
   $$v_p((n^2)!) \geq n \cdot v_p(n!)$$

Conclusion #

Since this inequality holds for every prime $p$, every prime factor in $(n!)^n$ appears with at least as much frequency in $(n^2)!$. This means $(n!)^n$ divides $(n^2)!$ for all natural numbers $n$.

内容的提问来源于stack exchange，提问作者Pranesh Ranjan Das