Let $n = p_1^{q_1}p_2^{q_2}p_3^{q_3}\dots p_n^{q_n}$ where each $p_i$ is a prime and less than $n$ and each $q_i \geq 1$.
We are required to prove that $n |(n-1)!$. For this to be true every $p_i$ has to be in the prime factorization of $(n-1)!$ and $q_i$ has to be less than or equal to the power of $p_i$ in $(n-1)!$. Now, $(n-1)! = 1\cdot 2\cdot3 \dots (n-1)$. Since each $p_i$ is less than $n$ it has to come atleast once in the factorial representation.
Now, it remains to be proven that there are greater than or equal to $q_i$ multiples of $p_i$ in the factorial representation of $(n-1)!$. There will be exactly $\left \lfloor{\frac{(n-1)}{p_i}}\right \rfloor $ multiples of $p_i$ in the factorial representation of $(n-1)!$. Since $\left \lfloor{\frac{(n-1)}{p_i}}\right \rfloor = \frac{n}{p_i} – 1 = ap_i^{q_i – 1} – 1$, where $a = \frac{n}{p_i^{q_i}} \geq 1$. I don't know how to prove that this is greater than or equal to $q_i$.
Best Answer
Two cases, depends on whether $n$ is a perfect square of a prime,
Case 1: if $n$ is not,
Let $n = qr$ where $q$ and $r$ are different integers smaller than $n$. Then both $q$ and $r$ are factors of $(n-1)!$.
Case 2: if $n = p^2$,
$p^2$ can still be a factor of $(n-1)!$ if there are both a $p$ factor and a $2p$ factor inside $(n-1)!$, which is when the following inequality holds: $$\begin{align*} n-1 &\ge 2p\\ (n-1)^2 &\ge 4n\\ n^2-6n+1 &\ge 0\\ n&\ge 6 \end{align*}$$