12
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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, $\endgroup$ – erfan soheil Dec 11 '14 at 20:18
  • 2
    $\begingroup$ 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. $\endgroup$ – Martin Brandenburg Dec 11 '14 at 21:01
  • $\begingroup$ @MartinBrandenburg what do you think about induction here ? $\endgroup$ – Maman Dec 11 '14 at 21:10
  • 1
    $\begingroup$ 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. $\endgroup$ – Martin Brandenburg Dec 11 '14 at 22:05
  • 2
    $\begingroup$ 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. $\endgroup$ – Martin Brandenburg Dec 12 '14 at 19:57
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I will dig your proof when I will be ok with p-adic valuation ! Nice try but it diverges from basic arithmetic $\endgroup$ – Maman Dec 14 '14 at 13:27
  • $\begingroup$ @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. $\endgroup$ – Martin Brandenburg Dec 14 '14 at 13:29
  • $\begingroup$ I didn't study p-adic valuation yet $\endgroup$ – Maman Dec 14 '14 at 13:30
  • 1
    $\begingroup$ Yes and that's OK. This is not needed. $\endgroup$ – Martin Brandenburg Dec 14 '14 at 13:31
1
$\begingroup$

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

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

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.

$\endgroup$
  • $\begingroup$ Here you did the case where $n+1>p$ when $p$ divides $n+1$ and you have directly decomposed $n+1$ into prime factors ? $\endgroup$ – Maman Dec 14 '14 at 22:16
  • $\begingroup$ 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. $\endgroup$ – alex.jordan Dec 14 '14 at 23:05
  • $\begingroup$ 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... $\endgroup$ – Maman Dec 14 '14 at 23:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.