$\prod_{i=0}^{n-1}(2^n-2^i)$ can be divided by $n!$

Question

My student asked me the following question:

Prove that for any natural number $n \geq 2$, the product $$\prod_{i=0}^{n-1}(2^n-2^i)$$ is divisible by $n!$.

I would like to ask for a nice solution to this question. My idea was using induction and Fermat's little theorem.

Answer 1

A nice solution is given by the natural embedding of $S_n$ into $\mathrm{GL}_n(\mathbb{F}_2)$.

Here $S_n$ is the symmetric group of $n$ elements. Every element of $S_n$ permutes the canonical basis of $\mathbb{F}_2^n$, hence gives an $\mathbb{F}_2$-linear automorphism of $\mathbb{F}_2^n$. This embeds $S_n$ as a subgroup of $\mathrm{GL}_n(\mathbb{F}_2)$.

Now it only remains to say that the cardinalities of the two groups are $n!$ and $\prod_{i = 0}^{n - 1}(2^n - 2^i)$, respectively.

---

By replacing $\mathbb{F}_2$ with $\mathbb{F}_q$ for any prime power $q$, one proves in the same way that $n!$ divides $\prod_{i = 0}^{n - 1}(q^n - q^i)$.

Answer 2

Hint For each odd prime $p$, if $p^k |m \leq n$ then $$p^k |2^{\frac{p-1}{p}m}-1$$ and hence $$p^k| 2^{n}-2^{n-\frac{p-1}{p}m}$$