Estonian Mathematical Olympiad

For any prime $p$, $p^2\nmid p!$ as prime $p$ occurs only once in the prime factorization of $p!$. Additionally, $4^2=16$ does not divide $4!=24$. We will show that $n^2\mid n!$ for all other positive integers $n$. Let $p$ be a prime factor of $n$, and $k$ the exponent of $p$ in the prime factorization of $n$. If there exists a different prime factor $q$ of $n$, then both $p^k$ and $p^{k}q$ are in the set of integers from 1 to $n$ and hence $p^{2k}\mid n!$. This holds for all prime factors $p$ of $n$.

Thus $n^2$ divides $n!$ for all $n$ with at least two distinct prime factors. Now consider the remaining integers $n=p^k$ for prime $p$. For $k\ge 3$ all three integers $p$, $p^{k-1}$, and $p^k$ are distinct factors in $n!$, implying that $p^{2k}=n^2$ divides $n!$. For $k=2$ and $p>2$ the integers $p$, $2p$, and $p^2$ are distinct factors in $n!$, implying that $p^4=n^2$ divides $n!$.

---

Alternative solution.

We find all positive integers $n$ such that $n\mid (n-1)!$; obviously this condition is equivalent to that of the problem. For prime $n$, no integer less than $n$ can have a prime factor $n$ and thus $n$ cannot divide $(n-1)!$. For $n=4=2^2$, 4 does not divide $(n-1)!=6$. On the other hand, for $n=p^2$ where $p>2$ is prime, the integers $p$ and $2p$ are in the set of integers from 1 to $n-1$, implying $p^2=n\mid (n-1)!$. If $n$ is a cube or a higher power of some prime, or has at least two prime factors, then it obviously has a divisor $d$ such that $1<d<n$ and $d^2\ne n$ (e.g. the smallest prime factor of $n$). Hence $d$ and $\frac{n}{d}$ are distinct positive integers less than $n$ and their product $n$ divides $(n-1)!$.