4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ $4\nmid(4-1)!{}$ $\endgroup$ – anon Aug 15 '13 at 8:01
  • $\begingroup$ I forgot to mention the constraint that $n > 4$ $\endgroup$ – Gerard Aug 15 '13 at 8:03
  • 1
    $\begingroup$ 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).$$ $\endgroup$ – anon Aug 15 '13 at 8:04
  • $\begingroup$ 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? $\endgroup$ – Prahlad Vaidyanathan Aug 15 '13 at 9:07
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ What if $n = p^k$, $k > 1$? $\endgroup$ – Michael Albanese Aug 15 '13 at 7:59
  • $\begingroup$ @Michael: Yes, I should have said something about that case. $\endgroup$ – Brian M. Scott Aug 15 '13 at 8:04
  • $\begingroup$ 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$. $\endgroup$ – Gerard Aug 15 '13 at 8:07
7
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.