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}$

Question

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)

Thanks in advance.

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...

Answer 1

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$.

Answer 2

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)$.

Answer 3

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.