Let $p$ be a prime and $n$ be a positive integer. Prove that $n! $ divides $(p^n-1)\cdots(p^n-p^{n-1})$ Let $p$ be a prime and $n$ be a positive integer. Prove that $n! $ divides $$(p^n-1)(p^n-p)(p^n-p^2)\cdots(p^n-p^{n-1})$$
I have checked that it is trivial for $n=3,4$ But cant do the generalised part.
I have also got a group theoretic solution, but I want an elementary number theoretic solution.
 A: This is loosely related to the "count $GL_n(\mathbb F_p)$ approach," but more direct.
More generally, $$(p^n-1)(p^n-p)\cdots(p^{n}-p^{k-1})$$ is divisible by $k!$. This is because this counts the number of ordered sequences $v_1,v_2,v_3,\dots,v_k$ of linear independent vectors in $\mathbb F_p^n$. But for every unordered set of $k$ linear independent vectors, there are $k!$ ordered sequences of $k$ linear independent vectors. So if $M_k$ is the number of sets of $k$ linear independent vectors, then:
$$k!M_k = (p^n-1)\cdots (p^n-p^{k-1})$$

Alternatively, you can try to figure out the high power of a prime $q$ which divides $M=(p^n-1)\cdots(p^n-p^{n-1})$, where $q\leq n$. 
The highest power of the prime $q$ which divides $n!$ is $$N_q=\sum_{k=1}^{\infty}\left\lfloor\frac n{q^k}\right\rfloor$$
If $q=p$, then $q^{n(n-1)/2}\mid M$ and $\frac{n(n-1)}{2}\geq N_q$.
If $q\neq p$, then the highest power of $q$ which divides $M$ is at least:
$$\sum_{k=1}^{\infty}\left\lfloor\frac n{q^k-q^{k-1}}\right\rfloor$$
The is because at least every $q-1$ values of $p^{a}-1$ are divisible by $q$, at least every $q^2-q$ is divisible by $q^2$, at least every $q^3-q^2$ is divisible by $q^3$. This is because the order of $p$ modulo $q$ is at most $q-1$, the order of $p$ modulo $q^2$ is at most $q^2-q$, etc.
But it is clear that:
$$\sum_{k=1}^{\infty}\left\lfloor\frac n{q^k-q^{k-1}}\right\rfloor\geq \sum_{k=1}^{\infty}\left\lfloor\frac n{q^k}\right\rfloor$$
I believe this proof extends to $p$ not a prime. If $p$ is not prime, show it for $q\mid p$ and then for $(q,p)=1$. 
A: This may not qualify as elementary number theory, but it could be a fruitful way to look at this and similar problems.  The result follows from the theory of Bhargava factorials, and $p$ need not be prime.  Example 18 in this paper states $n!_T = (p^n-1)(p^n-p)(p^n-p^2)\cdots(p^n - p^{n-1})$ for the set $T = \{1, p, p^2, p^3, \dots\}$ for any integer $p > 1$.  The usual factorial is $n!_S = n!$ for $S = \mathbb{Z}$.  But Lemma 13 states that $n!_S \,|\, n!_T$ for all $n \ge 0$ whenever $T \subseteq S$.
A: Pulling out powers we find $$A = (p^n - 1)~p~(p^{n-1} - 1)~p^2(p^{n-2} - 1)~\dots~p^{n-1}~(p-1),$$
so that more compactly one has $$A=p^{n(n-1)/2}\prod_{k=1}^n(p^k-1).$$
Suppose the prime factorization of $n!$ contains the prime $q$ with exponent $t$; can we bound this exponent? Well, $\lfloor n/q\rfloor$ terms are divisible by $q$ at least once, and then $\lfloor n/q^2\rfloor$ are divisible by $q$ at least twice, and so on -- so this means that the actual sum is $t=\sum_{i=1}^\infty \lfloor n/q^i\rfloor$ and that $t\le\left\lfloor\sum_{i=1}^\infty n/q^i\right\rfloor$ should act as an upper bound, giving $t \le \lfloor n/(q - 1)\rfloor$ when the geometric series is summed. 
Therefore if $q=p$ we find directly that the divisors must fit into the first term, $t < n(n-1)/2$, and this is certainly possible since our upper bound on $t$, $n/(p-1),$ is less than $n(n-1)/2$ whenever $2 < (n-1)(p-1).$ (Special cases created: $n=1$ unconditionally and $(n, p) = (2, 2).$ Both can be easily verified; $1!$ divides anything and $2!$ divides $6$.)
For $q \ne p$ we have a bit of a thornier problem.  Fermat's little theorem gives us that $p^{q-1}\equiv 1 \pmod q$ and successive powers of the prime must also be equivalent to $1$ mod $q$, so we have that $p^{m(q-1)} - 1\equiv 0\pmod q$ for $m=1,2,\dots$. As we enumerate $k:1\to n$ we must hit these terms $\lfloor n/(q-1) \rfloor$ times and therefore the right hand side must be divisible by $q^{\lfloor n/(q-1)\rfloor}$ which implies that it is divisible by $q^t,$ completing the proof.
