Kanunnikov A.L.

For each prime $p$, find the greatest natural power of the number $p$ !, by which the number $(p^2)!$ is divisible.
If $\left(p^{2}\right)!$ is divisible by $(p!)^{n}$, then $n \leq p+1$, since $p$ enters the factorization of the number $p!$ into prime factors with an exponent of 1 (and thus in the factorization of the number $(p!)^{n}$ - with an exponent of $n$), while in the factorization of the number $(p^{2})!$ - with an exponent of $p+1$. We will prove that $\left(p^{2}\right)!$ is divisible by $(p!)^{p+1}$.

First method. Write $p^{2}$ different elements in the form of a $p \times p$ table. There are $(p^{2})!$ such tables. Two tables are called equivalent if one can be obtained from the other by some permutations of elements within rows, as well as some permutation of the rows themselves (a total of $p+1$ permutations of $p$ objects). In each equivalence class, there are $(p!)^{p+1}$ tables. Therefore, $(p^{2})!$ is divisible by $(p!)^{p+1}$.

Second method. $\frac{\left(p^{2}\right)!}{(p!)^{p}}=\prod_{k=1}^{p} C_{p k}^{p}$ is divisible by $p!$, since $C_{p k}^{p}=\frac{p k(p k-1) \ldots(p k-p+1)}{p!}=k C_{p k-1}^{p-1}$ is divisible by $k$ for all $k \leq p$.

Third method. Take an arbitrary prime number $q \leq p$ and prove that in the factorization of the number $(p!)^{p+1}$ into prime factors, it enters with an exponent no greater than in the factorization of the number $(p^{2})!$.

Let $q^{n} \leq p<q^{n+1}$, then $q^{2 n} \leq p^{2}<q^{2 n+2}$. By Legendre's formula (see problem $\underline{60553}$), it is sufficient to check that

$$
(p+1)\left(\left[\frac{p}{q}\right]+\left[\frac{p}{q^{2}}\right]+\ldots+\left[\frac{p}{q^{n}}\right]\right) \leq\left[\frac{p^{2}}{q}\right]+\left[\frac{p^{2}}{q^{2}}\right]+\ldots+\left[\frac{p^{2}}{q^{2 n+1}}\right]
$$

From the obvious inequality $k[x] \leq[k x]$, it follows that

$p\left(\left[\frac{p}{q}\right]+\left[\frac{p}{q^{2}}\right]+\ldots+\left[\frac{p}{q^{n}}\right]\right) \leq\left[\frac{p^{2}}{q}\right]+\left[\frac{p^{2}}{q^{2}}\right]+\ldots+\left[\frac{p^{2}}{q^{n}}\right]$

Moreover, $\left[\frac{p}{q}\right]+\left[\frac{p}{q^{2}}\right]+\ldots+\left[\frac{p}{q^{n}}\right]=\left[\frac{p q^{n}}{q^{n+1}}\right]+\left[\frac{p q^{n}}{q^{n+2}}\right]+\ldots+\left[\frac{p q^{n}}{q^{2 n}}\right] \leq$

$\left[\frac{p^{2}}{q^{n+1}}\right]+\left[\frac{p^{2}}{q^{n+2}}\right]+\ldots+\left[\frac{p^{2}}{q^{2 n}}\right]$

## Answer

$p+1$.