# Prove that if $n > 4$ is composite $n|(n-1)!$

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$.

• $4\nmid(4-1)!{}$ – anon Aug 15 '13 at 8:01
• I forgot to mention the constraint that $n > 4$ – Gerard Aug 15 '13 at 8:03
• If $1<p_1^{e_1}<p_2^{e_2}<\cdots<p_k^{e_k}<n=p_1^{e_1}\cdots p_k^{e_k}$ with $k>1$ then $$(n-1)!=1\times\cdot\cdot\times \, p_1^{e_1}\times\cdot\cdot\times \, p_2^{e_2}\times\cdot\cdot\cdot\cdot\times \, p_k^{e_k}\times\cdot\cdot\times(n-1).$$ – anon Aug 15 '13 at 8:04
• If $n\neq p^2$ for any prime $p$, then $n = mk$ for $0 < m < k \leq (n-1)$, so $n\mid (n-1)!$. If $n = p^2$, then both $p$ and $2p$ occur in $(n-1)!$, so $n \mid (n-1)!$. Am I missing something? – Prahlad Vaidyanathan Aug 15 '13 at 9:07

HINT: You should not be using $n$ for both the number and the number of distinct prime factors: let $n=p_1^{q_1}p_2^{q_2}\ldots p_m^{q_m}$ instead. Now note that $p_i^{q_i}<n$ for $i=1,\dots,m$, and the factors $p_i^{q_i}$ are all distinct. This covers the case $m>1$.

If $n=p^k$ for some $k>1$, you can directly count the number of factors of $p$ in $n!$. For example, $p^2!$ has factors $p,2p,\ldots,(p-1)p$, which contribute $p$ factors of $p$; that’s enough even if $p=2$. Other powers are almost as easy, but you don’t actually need them: if $k>2$, note that $p<p^{k-1}<n$.

• What if $n = p^k$, $k > 1$? – Michael Albanese Aug 15 '13 at 7:59
• @Michael: Yes, I should have said something about that case. – Brian M. Scott Aug 15 '13 at 8:04
• That case can be treated separately and we can say that $(n-1)! = 1\cdot 2\cdot...p...2p...3p...n$ and that there are exactly $\frac{n}{p} - 1 = p^{k-1} - 1$ multiples of $p$ in the representation of $(n-1)!$, which is clearly greater than or equal to $k$. – Gerard Aug 15 '13 at 8:07

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*}

Here's a slightly easier argument. It uses the same idea, just with less factors.

Let $n = ab$ with $1 < a, b < n$ (such $a$ and $b$ exist because $n$ is composite). If $a$ and $b$ are distinct, then they both occur in the product $(n-1)! = (n-1)\times (n-1)\times \dots \times 2\times 1$.

The only time we can't arrange $a$ and $b$ to be distinct is if $n = p^2$ for some prime $p$. As $n > 4$, $p \geq 3$. Now note that the numbers $p, 2p, \dots, (p-1)p$ are all less than $n - 1$ so $p^{p-1} \mid (n - 1)!$. In particular, $p - 1 \geq 2$, so $p^2 \mid p^{p-1}$ and therefore $p^2 \mid (n-1)!$.