Factorial Divides Product of Successive Numbers
Jump to navigation
Jump to search
Theorem
Let $m, n \in \N_{\ge 1}$ be natural numbers
Let $m^{\overline n}$ be $m$ to the power of $n$ rising.
Then:
- $m^{\overline n} \equiv 0 \bmod n!$
That is, the factorial of $n$ divides the product of $n$ successive numbers.
Proof
Let $m \in \N_{\ge 1}$.
Consider the set:
- $S = \{ {m, m + 1, m + 2, \ldots, m + n - 1 }\}$
Note $S$ has $n$ elements.
By Set of Successive Numbers contains Unique Multiple:
- $\left\{ {m} \right\}$ contains a factor of $1$,
- $\left\{ {m, m+1} \right\}$ contains a factor of $2$,
and in general,
- $\left\{ {m, m+1, \ldots, m + j - 1} \right\}$ contains a factor of $j$.
It follows that $S$ contains factors of $1, 2, 3, \ldots, n$.
Multiplying all elements of $S$ gives:
\(\ds m \left({m+1}\right)\ldots\left({m+n-1}\right)\) | \(=\) | \(\ds k_1 2 k_2 3 k_3 \ldots \left({n-1}\right)k_{n-1} n k_n\) | for some $k_1, k_2, \ldots, k_n \in N$ | |||||||||||
\(\ds \) | \(=\) | \(\ds \left({k_1 k_2 \ldots k_{n-1}k_n}\right)\left({1 \times 2 \times \ldots \times \left({n - 1}\right) \times n}\right)\) | ||||||||||||
\(\ds \implies \ \ \) | \(\ds m^{\overline n}\) | \(=\) | \(\ds K n!\) | for some $K \in \N$ | ||||||||||
\(\ds \implies \ \ \) | \(\ds m^{\overline n}\) | \(\equiv\) | \(\ds 0 \bmod n!\) |
$\blacksquare$