# Show that $(\binom{p^2}{p} -p )$ is divisible by $p^5$, for every prime number $p, p\ge 5$

Show that $$(\binom{p^2}{p} -p )$$ is divisible by $$p^5$$, for every prime number $$p, p\ge 5$$.

I have a combinatorics problem, and this is what it reduces to. I am not quite sure how to link the fifth power in divisiblity.

Edit: I have shown this is equivalent to $$(p-1)!\cdot(\sum_{i=1}^{p-1} \frac{1}{i}) \equiv 0 \pmod {p^2}$$

• Can you give the original problem? – Phicar Apr 15 at 19:10
• Show that the number of ways to choose p positions on a p x p matrix, such that the p elements aren't all on the same row, is divisible by p^5 – Parallelism Alert Apr 15 at 19:17
• :P that's what i was thinking. – Phicar Apr 15 at 19:19
• was it a chessboard problem ? – Roddy MacPhee Apr 15 at 19:19
• Yes, it was a chessboard problem. – Parallelism Alert Apr 15 at 19:20

## 2 Answers

Since $$\binom{p^2}p = \frac{p^2(p^2-1)\dotsb(p^2-(p-1))}{1\cdot2\dotsb(p-1)p},$$ we want to show that $$\frac{(p^2-1)\dotsb(p^2-(p-1))}{1\cdot2\dotsb(p-1)} \equiv 1 \pmod{p^4};$$ that is, $$(p^2-1)\dotsb(p^2-(p-1)) \equiv (p-1)! \pmod{p^4}.$$ Opening the parentheses in the LHS and observing that $$(-1)(-2)\dotsb(-(p-1))=(p-1)!$$, it remains to show that the sum of all $$p-1$$ terms divisible by $$p^2$$ but not by $$p^4$$ is $$0$$ mod $$p^4$$; that is, considering the polynomial
$$P(x) := (x-1)(x-2)\dotsb(x-(p-1)),$$ we want to show that the coefficient of the linear term of this polynomial is $$0$$ mod $$p^2$$.

To this end we make two observations. The first is nearly trivial: $$P(p-x) = P(x). \tag{1}$$ The second observation is that the polynomial $$P(x)-(x^{p-1}-1)$$ has degree at most $$p-2$$, while the value of this polynomial at every integer point is divisible by $$p$$ (hint: use Wilson's theorem for $$x\equiv 0\pmod p$$); consequently, $$P(x) = (x^{p-1}-1) + pQ(x), \tag{2}$$ where $$Q$$ is a polynomial with integer coefficients.

Substituting (1) into (2), we get $$(p-x)^{p-1}-1+pQ(p-x) = x^{p-1}-1+pQ(x),$$ which, in view of $$(p-x)^{p-1}\equiv x^{p-1}-(p-1)px^{p-2}\pmod{p^2}$$, yields $$pQ(p-x) \equiv (p-1)px^{p-2} + pQ(x) \pmod{p^2};$$ that is, $$Q(p-x) \equiv Q(x)-x^{p-2} \pmod p.$$ But $$Q(p-x)\equiv Q(-x)\pmod p$$; therefore $$Q(-x)\equiv Q(x)-x^{p-2}\pmod p,$$ and it follows that the linear terms of $$Q(-x)$$ and $$Q(x)$$ vanish mod $$p$$. Now by (2), the linear term of $$P$$ is divisible by $$p^2$$. This completes the proof.

• Well, not quite "all resulting summands". You have to add the ones with a $p^2$ together, and even then I'm not sure. – darij grinberg Apr 15 at 19:36
• How do you see the next term is divisible by $p^4$ and not just $p^3$? – Nate Apr 15 at 19:36
• I think your answer (once corrected a bit) perfectly complements the other :) – darij grinberg Apr 15 at 19:46
• @darijgrinberg: Took me a while, but seems eventually correct. – W-t-P Apr 16 at 15:53
• Nice work! Let me remark that your equality (2) (or, rather, the existence of a polynomial $Q\left(x\right) \in \mathbb{Z}\left[x\right]$ that satisfies it) is easier to prove by working over the finite field $\mathbb{F}_p$ than by working over the ring $\mathbb{Z}$. Indeed, over $\mathbb{F}_p$, the polynomial $\left(x-1\right)\left(x-2\right)\cdots\left(x-\left(p-1\right)\right) - \left(x^{p-1} - 1\right)$ has degree $\leq p-2$ and has at least $p-1$ distinct roots (namely, the residue classes of $1, 2, \ldots, p-1$, because of Fermat's Little); thus, this polynomial must be $0$. Hence, ... – darij grinberg Apr 16 at 20:06

It's sufficient to prove that $$\sum\limits_{i=1}^{p-1} \frac{1}{i} \equiv 0 \pmod {p^2}$$. Denote $$S=\sum\limits_{i=1}^{p-1} \frac{1}{i}$$. Then, note that $$2S=\sum\limits_{i=1}^{p-1} \left(\frac{1}{i}+\frac{1}{p-i}\right)= p\cdot \sum\limits_{i=1}^{p-1} \frac{1}{i(p-i)}.$$ Hence, it's sufficient (since $$p>3$$) to prove that $$\sum\limits_{i=1}^{p-1}\frac{1}{i(p-i)}\equiv 0\pmod p.$$ However, $$\sum\limits_{i=1}^{p-1}\frac{1}{i(p-i)}\equiv -\sum\limits_{i=1}^{p-1}\frac{1}{i^2}\pmod p.$$ Since modulo $$p$$ we have $$\{1,2,\ldots, p-1\}=\left\{\frac{1}{1},\frac{1}{2},\ldots, \frac{1}{p-1}\right\}$$ we obtain $$\sum\limits_{i=1}^{p-1}\frac{1}{i^2}\equiv \sum\limits_{i=1}^{p-1} i^2=\frac{p(p-1)(2p-1)}{6}\equiv 0\pmod p$$ for prime $$p\geq 5$$. Thus, $$\sum\limits_{i=1}^{p-1} \frac{1}{i^2} \equiv 0 \pmod {p}$$ and so $$\sum\limits_{i=1}^{p-1} \frac{1}{i} \equiv 0 \pmod {p^2}$$, as desired.

• I am not following what comes after the "Hence it is sufficient..."Why does $\sum_{i=1}^{p-1} \frac{1}{i(p-i)} \equiv 0$ mod $p$ imply $\sum_{i=1}^{p-1} \frac{1}{p} \equiv 0$ mod $p^2$? For $p>5$ of course – Mike Apr 15 at 20:39
• nevermind whoops – Mike Apr 15 at 20:52