Show that $n! \mid (p^n-1)(p^n-p) \cdots (p^n-p^{n-1})$ where $p$ is prime and $n \geq 1$. So, I'm preparing for an exam and in one of the problems it asks us to find the number of distinct bases that we can have for an $n$ dimensional vector space over a finite field of $p$ elements ($p$ is a prime number, of course).
So, I started to reason this way: First I decided to solve it by simplifying the problem with putting an order. For the first vector, I can choose $p^n -1$ elements in $F^n$ because $0$ can't be chosen. For the second vector, I can choose $p^n - p$ elements because the second vector shouldn't lie in the span of the first vector. For the third vector I can choose $p^n - p^2$ vectors that don't lie in the span of the previously chosen vectors. Continuing with this reasoning I will have $p^n - p^{n-1}$ choices for the $n$-th vector in my basis set. Then since order does not matter in the problem, I have to divide by $n!$ to find the number of distinct bases without considering the order. It seems like I have solved the problem, but then a question popped up in my mind.
Does $n!$ really divide $(p^n-1)(p^n-p)(p^n-p^2)\cdots(p^n-p^{n-1})$ for $n \geq 1$ where $p$ is a prime number? 
This counting formula shows that it must be true, but I'm looking for a number theoretic proof if possible or some argument that is independent from this combinatorial proof that I have.
 A: Your counting proof is a fine proof.
Alternatively, given any other prime $q$, find the highest power of $q$ that divides $n!$. Show that it is less than or equal to the highest power of $q$ that divides $(p-1)(p^2-1)\cdots(p^n-1)$.
Then you just need to deal with the case of $q=p$.
That's not a particularly direct proof, however.
This proof will work for $p$ not a prime, then just break the cases into $q\mid p$ and $q\not\mid p$.
Specifically, the number of time $q$ goes into $n!$ is:
$$\sum_{k=1}^\infty \left\lfloor\frac n {q^k}\right\rfloor$$
But we can show, by similar reason, that, if $q\not\mid p$, then $q$ goes into $(p-1)(p^2-1)\cdots(p^n-1)$ at least:
$$\sum_{k=1}^\infty \left\lfloor\frac n {\phi(q^k)}\right\rfloor$$
times. This is because, if $\phi(q^k)\mid m$ then $q^k\mid p^m-1$.
Since $\phi(q^k)<q^k$, we see that $ \left\lfloor\frac n {q^k}\right\rfloor\leq  \left\lfloor\frac n {\phi(q^k)}\right\rfloor$ for each $k$. So $q$ goes into $n!$ no more times than $q$ goes into $(p-1)(p^2-1)\cdots(p^n-1)$.
I'm wondering if there is a combinatorial proof for the general $p$ - the counting proof in the question only generalizes for $p$ a prime power.
