I'm trying to prove the following:
$m^{\overline n} \equiv 0 \bmod n!$
Where $m^{\overline n} = m\left({m+1}\right)\left({m+2}\right)\ldots\left({m+n-1}\right)$, the product of $n$ successive natural numbers $\ge 1$.
I tried induction, but couldn't figure out how to make the induction step.
I also tried assuming the negation and then reducing it to a system of congruences $\bmod n!$:
$m \equiv 1, 2, \ldots, n!-1$
$m+1 \equiv 1, 2, \ldots, n!-1$
$\vdots$
$m + n - 1 \equiv 1, 2, \ldots, n!-1$
but couldn't get a contradiction.
My intuition tells me that this can be proved using the pigeonhole principle. That is, my hunch is that $\left\{m, m+1, m+2, \ldots, m+n-1\right\}$ has to contain the factors of $n!$. Is my intuition correct? If not, how else should I prove this?
The simplest proof of this I know is that the binomial coefficient $\binom ab$ is an integer for suitably chosen $a$ and $b$. There are combinatorial proofs and induction proofs of that.
I mention this because the link with binomial coefficients does not seem to be mentioned very often in this context, yet the problems are identical.