# Prove that $\frac{(p^{n}-1)(p^{n}-p)…(p^{n}-p^{n-1})}{n!} \in \mathbb{N}$ with $p$ a prime number and $n \in \mathbb{N}$

Apparently this question requires a method linked with linear algebra but I was wondering if it was possible to solve it in a formal way like an induction on $n$ or by using an identity for $p^{n}-1$ ?

And also, why the condition $p$ a prime number, is necessary ? (I see why)

PS : Here is my try with an induction on $n$ :

Let $K_{n}=\frac{(p^{n}-1)(p^{n}-p).....(p^{n}-p^{n-1})}{n!}$

If $n=0$ then $K_{0}=0 \in \mathbb{N}$.

If $n=1$ then $K_{1}=p-1 \in \mathbb{N}$.

If $n=2$ then $K_{2}= \frac{(p^{2}-1)(p^{2}-p)}{2}=\frac{(p-1)^{2}p(p+1)}{2}$

In this case if $p=2$ then $2$ divides $6$ so $K_2 \in \mathbb{N}$. And if $p>2$ then we have $p-1$ even so $(p-1)^2$ is even and also $p+1$. $p$ is odd but when we multiply the three numbers we obtain an even number so if $p>2$ then $K_2 \in \mathbb{N}$.

Now, try to prove that $K_{n+1} \in \mathbb{N}$ :

$K_{n+1}=\frac{(p^{n+1}-1)(p^{n+1}-p).....(p^{n+1}-p^{n})}{(n+1)!} = \frac{(p^{n+1}-1)p^{n}}{n+1} \times \frac{(p^{n}-1)(p^{n}-p).....(p^{n}-p^{n-1})}{n!} = \frac{p^{2n+1}-1}{n+1} \times K_n$

with $K_n \in \mathbb{N}$.

Then I want to prove that $n+1$ divides $p^{2n+1}-p^{n}$

So for $p>n+1$ we have $n+1$ which is prime with $p$ for all $n\in \mathbb{N}$

That means that $p \equiv 1 [n+1] \Rightarrow p^{2n+1} \equiv 1 [n+1] \Rightarrow p^{2n+1}-p^{n} \equiv 0 [n+1]$.

Moreover if $p=n+1$ we take this expression $\frac{(p^{n+1}-1)p^{n}}{p}=(p^{n+1}-1)p^{n-1} \in \mathbb{N}$

It works, but if $p< n+1$, I don't know how to start...

• I khow $\frac{(p^{n}-1)(p^{n}-p).....(p^{n}-p^{n-1})}{n!}$ is the number of $n \times n$ nonsingular matrix in field $\Bbb F$ whit $p$ element, – erfan soheil Dec 11 '14 at 20:18
• No, the fraction is the number of unordered bases of $\mathbb{F}_p^n$ over $\mathbb{F}_p$. The invertible matrices correspond to ordered bases. – Martin Brandenburg Dec 11 '14 at 21:01
• @MartinBrandenburg what do you think about induction here ? – Maman Dec 11 '14 at 21:10
• Induction on $n$ won't work. But maybe induction on $0 \leq k \leq n$ works to show that $\frac{(p^n-1)(p^n-p) \cdots (p^n-p^{k-1})}{k!}$ is an integer. This is the number of linearly independent subsets of $\mathbb{F}_p^n$ of size $k$. I don't see how to do it as a calculation without linear algebra. – Martin Brandenburg Dec 11 '14 at 22:05
• Once again: Induction on $n$ won't work. This has "geometric" reasons (thinking about the variety $\mathrm{GL}_n/\Sigma_n$). In your attempt, $n+1 | p^{2n+1}-1$ is not true. – Martin Brandenburg Dec 12 '14 at 19:57

I've got an idea how to solve this problem. The proof is not complete, but I am rather confident that one can complete it.

Let's show more generally that $k!$ divides $(p^n-1) \cdot \dotsc \cdot (p^n-p^{k-1})$. I believe that this is true for every integer $p$. Recall that the multiplicity of a prime number $q$ in $k!$ equals $$v_q(k!)=\sum_{\ell \geq 1} \bigl\lfloor \frac{k}{q^\ell} \bigr\rfloor.$$ Thus, it suffices to prove that the multiplicity of $q$ in the product $P=(p^n-1) \cdot \dotsc \cdot (p^n-p^{k-1})$ is at least that large. Now the idea is to decompose $P$ in partial products $P_\ell$ such that the multiplicity of $q$ in $P_\ell$ is at least $\lfloor \frac{k}{q^\ell} \rfloor$, so that in the end the multiplicity of $P$ is at least $\sum_\ell \lfloor \frac{k}{q^\ell} \rfloor$.

I can show at least that the multiplicity is at least $\lfloor \frac{k}{q} \rfloor$: Consider $P_i = (p^n-p^{i q}) \dotsc (p^n - p^{iq+q-1})$ for $i \leq \lfloor \frac{k}{q} \rfloor-1$, so that $\prod_i P_i$ divides $P$. Then $P_i \equiv 0 \bmod q$, since each power of $p$ is one the powers of $1,\dotsc,p^{q-1}$ modulo $q$. Hence, $q^{\lfloor \frac{k}{q} \rfloor}$ divides $P$.

• I will dig your proof when I will be ok with p-adic valuation ! Nice try but it diverges from basic arithmetic – Maman Dec 14 '14 at 13:27
• @Maman: I don't understand your comment. What is non-basic in my answer? I use prime factorizations, nothing else. The exponent of a prime in a prime factorization is called its multiplicity. – Martin Brandenburg Dec 14 '14 at 13:29
• I didn't study p-adic valuation yet – Maman Dec 14 '14 at 13:30
• Yes and that's OK. This is not needed. – Martin Brandenburg Dec 14 '14 at 13:31

Let $K$ be a field with $p$ elements.

Let $f(n,k)$ be the number of (unordered!) linearly independent sets of size $k$ in a $K$-vector space of dimension $n$. We have $f(n,0)=1$ for all $n$, as there is exactly one linearly independent set with zero elements. On the other hand, each of the $f(n,k)$ linearly independent sets of cardinal $k$ can be completed to a linearly independent set of cardinal $k+1$ in $p^n-p^k$ ways, but in this way each linearly independent set of $k+1$ elements is contructed $k+1$ times. It follows that $f(n,k+1)=f(n,k)(q^n-q^k)/(k+1)$.

• The question was not how to prove this with linear algebra, this is already well-known. The question is about a purely computational proof. – Martin Brandenburg Dec 14 '14 at 10:42
• It seems that in the last line should be $p$'s instead of $q$'s. – Alex Ravsky Nov 16 '16 at 20:52

Skipping your smaller base cases, fix a prime $p$ and, suppose $K_n$ is an integer for some $n$. You have $$K_{n+1}=\frac{(p^{n+1}-1)p^nK_n}{n+1}$$

Write $n+1=dp^a$, where $d$ is coprime to $p$. So $$K_{n+1}=\frac{(p^{dp^a}-1)p^nK_n}{dp^a}$$ $a$ is clearly no larger than $n$, so $p^a\mid{p^n}$.

At this point it would be nice if $d$ divides $p^{dp^a}-1$. But in general, it doesn't. For example, $3$ does not divide $5^{3\cdot5^0}-1=124$. This isn't quite a Fermat's Little Theorem situation, all though it almost looks like it is (and I fell for it too in an earlier version of this answer). So for the overall claim to be true (and we know it is using the linear algebra argument) $d$ must sometimes have factors that divide $K_n$ and not $(p^{n+1}-1)p^n$. So unless you strengthen your induction hypothesis to give information about what divides $K_n$, there is no hope of using induction to do this.

• Here you did the case where $n+1>p$ when $p$ divides $n+1$ and you have directly decomposed $n+1$ into prime factors ? – Maman Dec 14 '14 at 22:16
• This argument is regardless of $n+1\lesseqgtr p$. It just points out how $n+1$ is not always going to divide into $(p^{n+1}-1)p^n$. So your induction approach is not going to work. – alex.jordan Dec 14 '14 at 23:05
• Ok now I understand your argument but do I give up my proof ? I thought it would have worked if I solved the last case but apparently it didn't... – Maman Dec 14 '14 at 23:08