Is it true that $n!$ divides $p^n(p+1)(p^2+p+1)\cdots(p^{n-1}+\cdots+1)$?

Question

Let $p$ be a prime number (though I suspect that this might be true for composite ones as well). Define $$f(p,n)=\frac{p^n(p+1)(p^2+p+1)\cdots(p^{n-1}+\cdots+1)}{n!}$$ where $n$ is a positive integer. Show that $f$ is always an integer.

I tested this for a handful of $n,p$ values and it seems to be true. I managed to show that for every $m\le n$, we can find a $k\le n$ such that $$1+p+\cdots+p^k\equiv 0\qquad(\text{mod }m)$$ But I am stuck and can't go further.

Edit

Thanks to all the nice answers. Now that it's clear the answer to the title is yes, we can furthur relax the $p^n$ term and replace it by $$p^{\lfloor n/(p-1)\rfloor}$$ so that it disappears when $p>n$.

Answer 1

We show that, for any prime $q$, $\nu_q$ of the given quantity is $\geq 0$, which will imply the result.

Case 1. $q=p$. Then $\nu_p$ of the given quantity is $n-\nu_p(n!)$. Using Legendre's formula,

$$n-\nu_p(n!) = n-\frac{n-s_p(n)}{p-1}=n-\frac{n}{p-1}+\frac{s_p(n)}{p-1} \geq n\left(\frac{p-2}{p-1}\right)\geq \frac{n}{2}\geq 0$$

(here we have $s_p(n)$ is the sum of the digits of $p$ in base $n$).

Case 2. $q\neq p$. We may assume $q\leq n$, as otherwise $\nu_q$ of the denominator is $0$. Let $\mathrm{ord}_q(p)=d.$

Case 2.1. $d=1$. Here, we have $q|p-1$, so

$$\nu_q\left(\frac{p^k-1}{p-1}\right)=\nu_q(k)$$

by Lifting the Exponent. Thus, we have

$$\nu_q\left(\prod_{k=1}^n \frac{p^k-1}{p-1}\right)=\sum_{k=1}^n \nu_q\left(\frac{p^k-1}{p-1}\right)=\sum_{k=1}^n \nu_q(k)=\nu_q(n!).$$

Case 2.2 $d>1$. Let $v=\nu_q(p^d-1).$ Then we have, again by LTE, that

$$\nu_q\left(\frac{p^k-1}{p-1}\right)=v+\nu_q(k)$$

if $d|k$ and $0$ otherwise. So, $\nu_q$ of the numerator is

$$v\left\lfloor \frac{n}{d}\right\rfloor + \nu_q\left(\left\lfloor\frac{n}{d}\right\rfloor!\right).$$

Letting $m=\left\lfloor \frac{n}{d}\right\rfloor$ we see

$$vm+\nu_q(m!)\geq m+\frac{m-s_q(m)}{q-1} = \frac{mq-s_q(m)}{q-1}=\frac{mq-s_q(mq)}{q-1}=\nu_q((mq)!).$$ Now, we have that

$$\nu_q(n!)=\nu_q\left(q\left\lfloor\frac{n}{q}\right\rfloor\right).$$

Since

$$d\leq q-1\implies \frac{n}{d}\geq \frac{n}{q-1} > \frac{n}{q} \implies m\leq \left\lfloor\frac{n}{q}\right\rfloor,$$

we have

$$\nu_q((mq)!)\geq \nu_q(n!),$$

finishing the proof.

Answer 2

Original version:

This is not true for $n=2p$. The numerator has only one factor that is a multiple of $p$, but the denominator is divisible by $p^2$.

---

Edited version:

This can be seen as follows. Let $q$ be a prime $\le n$. It is well known that the highest power $q^\ell$ that is a factor of $n!$ has exponent $$ \ell=\lfloor \frac nq\rfloor+\lfloor\frac n{q^2}\rfloor+\cdots $$ (this is a finite sum as the terms become zero after $q^k$ exceeds $n$). This is because $n!$ has $\lfloor\dfrac n q\rfloor$ factors that are divisible by $q$, $\lfloor\dfrac n {q^2}\rfloor$ factors that are (additionally) divisible by $q^2$ et cetera. We need to show that the numerator is divisible by $q^\ell$ as well.

If $q=p$ the first factor takes care of everything because $n\ge\ell$.

Otherwise, let $t$ be the order of $p$ modulo $q$, i.e. $t$ is the smallest positive integer such that $p^t\equiv1\pmod q$. It is known (Little Fermat) that $t\mid q-1$. Another standard exercise shows that $$ p^{tq^m}\equiv 1\pmod {q^{m+1}} $$ for all integers $m\geq0$.

Now we are well places to study an individual factor $$ x(r)=1+p+p^2+\cdots+p^{r-1}=\frac{p^r-1}{p-1}. $$

Assume next that $p\not\equiv1\pmod q$. It follows that $x(r)$ is divisible by the same power of $q$ as $p^r-1$. So $x(r)$ is divisible by $q$ whenever $r$ is a multiple of $q-1$, divisible by $q^2$ whenever $r$ is a multiple of $q(q-1)$ et cetera. It follows immediately that $\prod_{r=1}^n x(r)$ is divisible by $q^\ell$.

This leaves the case of $q\mid p-1$. In this case $p^k\equiv 1\pmod q$ for all $k$, so $x(r)\equiv r\pmod q$. In particular, $x(r)$ is divisible by $q$ whenever $q\mid r$. However, we need a little bit more to get some of the factors $x(r)$ divisible by higher powers of $q$ as well. A way forward is to observe that if $p\equiv1\pmod{q^k}$ for some $k\ge0$, then, for all $i$ we have that $$p^{q^i}\equiv1\pmod {q^{k+i}}$$ for all $i\ge0$. This forces $x(r)$ to be divisible by $q^i$ whenever $r$ is. This settles the last case.

Answer 3

No.

Take $p=5$. Then of the polynomials $p$, $p+1$, $p^2+p+1$, $\ldots$ only the polynomial $p$ is divisible by 5.

Yet $n!$ is divisible by $5^{\lfloor\frac{n}{5} \rfloor}$.

[In fact the above argument holds for any $p$ and $n$ large enough relative to $p$; indeed $n!$ is divisble by $p^{\lfloor\frac{n}{p} \rfloor}$]

Answer 4

Let $q$ be a prime $\le n$. Then the maximal exponent $k$ such that $q^k$ divides $n$ is $$k=\lfloor n/q\rfloor +\lfloor n/q^2\rfloor+\lfloor n/q^3\rfloor+\ldots,$$ and this exponent is strictly less than $n/q+n/q^2+\ldots=\frac n{q-1}$, and in particular $k<n$.

If $p=q$, we see immediately that $q^k$ cancels against $p^n$.

For other $p$, let $s$ be minimal with $p\not\equiv 1\pmod {q^r}$. Then for $1\le \ell<s$, we have that $1+\ldots + p^{r-1}$ is a multiple of $q^\ell$ iff $\ell \mid r$, hence for $\lfloor n/q^\ell\rfloor$ of the factors. Moreover, we have that $1+p+\ldots + p^{r-1}=\frac{p^r-1}{p-1}\equiv0\pmod {q^s}$ whenever $r$ is a multipe of $\phi(q^s)=q^{s-1}(q-1)$, which happens for $\lfloor \frac n{q^{s-1}(q-1)}\rfloor$ of the factors. We conclude that the numerator contains $q$ to the power of $$ \sum_{\ell=1}^{s-1}\left\lfloor \frac n{q^\ell}\right\rfloor +\left\lfloor \frac n{q^{s-1}(q-1)}\right\rfloor.$$ In order to show that this is $\ge k$, it suffices to show $$ \sum_{\ell=s}^{\infty}\left\lfloor \frac n{q^\ell}\right\rfloor \le \left\lfloor \frac n{q^{s-1}(q-1)}\right\rfloor$$ But the left hand side is $<\sum_{\ell=s}^{\infty}\frac n{q^\ell}= \frac n{q^{s-1}(q-1)}$, and as it is an integer, the claim follows. Hence $q^k$ cancels against the numerator.

In summary, it follows that $n!$ cancles against the numberator.

Answer 5

Here's a sort of obnoxious proof. For $p$ a prime write

$$[n]_p = \frac{p^n - 1}{p - 1}$$

and

$$[n]_p! = [n]_p [n-1]_p \dots \dots [1]_p$$

(the $p$-factorial.)

The group $GL_n(\mathbb{F}_p)$ has order

$$(p^n - 1)(p^n - p) \dots (p^n - p^{n-1}) = p^{ {n \choose 2} } (p - 1)^n [n]_p!$$

and it contains a subgroup $G$ of order $(p - 1)^n n!$, namely the wreath product $\mathbb{F}_p^{\times} \wr S_n$; explicitly this is the group of permutation matrices whose nonzero entries can be any nonzero element of $\mathbb{F}_p^{\times}$. This implies that

$$\frac{|GL_n(\mathbb{F}_p)|}{|G|} = \frac{p^{ {n \choose 2} } [n]_p!}{n!}$$

is an integer, which gives the desired divisibility result at every prime except $p$, which can be handled as in the other answers; it annoys me that I don't see how to handle it by making the group $G$ slightly larger (we would need to enlarge it by a factor of $p^{ {n \choose 2} - n}$, for $n \ge 4$, and I don't see an obvious way to do that).

Incidentally, there is also a group-theoretic way to see that the largest power of $p$ dividing $n!$ is

$$\nu_p(n!) = \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \cdots$$

which is by finding a Sylow $p$-subgroup of $S_n$. This group is surprisingly complicated to describe explicitly but it can be constructed inductively on the $p$-adic expansion of $n$ by products of iterated wreath products of copies of the cyclic group $C_p$; for example in $S_p$ it's just the single copy of $C_p$ given by a $p$-cycle, in $S_{p^2}$ it's the wreath product $C_p \wr C_p$ whose elements look like a "$p$-cycle of $p$-cycles," etc.

This lovely trick of proving divisibility results using Lagrange's theorem has several other cute applications. For example $n! m!$ divides $(n + m)!$ because $S_n \times S_m$ is a subgroup of $S_{n+m}$; similarly $n!^m m!$ divides $(nm)!$ because the wreath product $S_n \wr S_m$ is a subgroup of $S_{nm}$. In the nicest cases you can not only find two groups $G$ and $H$ with the right orders but even give a clean interpretation of $G/H$.

Answer 6

By Euler's totient theorem $x^{\phi(n)} = 1\mod(n)$. This implies that $x^{\phi(n)-1}+x^{\phi(n)-2} +\dots+1= 0\mod(n)$ if $x\neq1$ and $(x,n)=1$. $\phi(p^k) = p^k-p^{k-1}$ when $p$ is prime. Therefore $\phi$ takes unique values on prime powers. (In other words it is injective when restricted to the prime powers.)

Therefore if we split $n!$ into a product of prime powers for each prime, for each prime power $q^k$ from the $n!$ on the denominator we can match with a unique $p^{\phi(q^k)-1}+p^{\phi(q^k)-2} +\dots+1$ on the numerator divisible by $q^k$, assuming $(q^k,p)=1$. (Hence the intermediate, quite natural result that if $p\neq1$ and $p>n$ then $n!$ divides $(p+1)(p^2+p+1)\cdots(p^{n-1}+\cdots+1)$)

If $(q^k,p)\neq1$ clearly $p=q$ and we can take care of this additional factor by adding $p^{\lceil \frac{n}{p-1}\rceil}$ to the numerator, hence the result. (I think you need the ceiling rather than the floor since $\frac{n}{p-1}$ is not necessarily an integer)