Does $n!$ divide $ n^n$? Today while I was reading on how to shuffle an array I came across a statement that claims we shall not swap an array entry with the whole array range when shuffling the array otherwise we end up with a biased result. Click here for details.
They demonstrated that by saying that $n!$ does not divide $n^n$ because $(n-1)$ divide $n!$ but at the same time $(n-1)$ does not share any prime factor with $n$, if I understood it right.
However, I did not grasp the "proof" given, so, can you help me figure out how to demonstrate it in a more rigorous approach?
 A: In the comments it is detailed how to find a prime $p$ such that $p \; \mid \; n-1$ but $p \; \nmid \; n^n$.
Suppose it were true now that $(n-1)! \; \mid \; n^n$.
Then we would have
$$
p \mid n -1 \mid (n-1)! \mid n^n
$$
so $p \mid n^n$, which is impossible.
A: No. Consider $4^4 = 2^{8}$, which has no 3 in its prime factorization, while $4! = 1 \cdot 2 \cdot 3 \cdot 4 = 2^3 \cdot 3$.
A: $\newcommand{\+}{^{\dagger}}%
 \newcommand{\angles}[1]{\left\langle #1 \right\rangle}%
 \newcommand{\braces}[1]{\left\lbrace #1 \right\rbrace}%
 \newcommand{\bracks}[1]{\left\lbrack #1 \right\rbrack}%
 \newcommand{\ceil}[1]{\,\left\lceil #1 \right\rceil\,}%
 \newcommand{\dd}{{\rm d}}%
 \newcommand{\down}{\downarrow}%
 \newcommand{\ds}[1]{\displaystyle{#1}}%
 \newcommand{\equalby}[1]{{#1 \atop {= \atop \vphantom{\huge A}}}}%
 \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}%
 \newcommand{\fermi}{\,{\rm f}}%
 \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,}%
 \newcommand{\half}{{1 \over 2}}%
 \newcommand{\ic}{{\rm i}}%
 \newcommand{\iff}{\Longleftrightarrow}
 \newcommand{\imp}{\Longrightarrow}%
 \newcommand{\isdiv}{\,\left.\right\vert\,}%
 \newcommand{\ket}[1]{\left\vert #1\right\rangle}%
 \newcommand{\ol}[1]{\overline{#1}}%
 \newcommand{\pars}[1]{\left( #1 \right)}%
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\pp}{{\cal P}}%
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,#2\,}\,}%
 \newcommand{\sech}{\,{\rm sech}}%
 \newcommand{\sgn}{\,{\rm sgn}}%
 \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}}
 \newcommand{\ul}[1]{\underline{#1}}%
 \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$
With Induction, you will use:
$$
{\pars{n + 1}^{n + 1} \over \pars{n + 1}!} = {\pars{n + 1}^{n} \over n!}
={n^{n} \over n!}\,{\pars{n + 1}^{n} \over n^{n}}
={n^{n} \over n!}\
\underbrace{\pars{1 + {1 \over n}}^{n}}
_{\ds{\not\in\ {\mathbb N}_{+}}}
$$
$\imp\quad n!\ \not\vert\ n^{n}$
