7
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ Can you give the original problem? $\endgroup$
    – Phicar
    Commented Apr 15, 2019 at 19:10
  • 1
    $\begingroup$ 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 $\endgroup$ Commented Apr 15, 2019 at 19:17
  • $\begingroup$ :P that's what i was thinking. $\endgroup$
    – Phicar
    Commented Apr 15, 2019 at 19:19
  • $\begingroup$ was it a chessboard problem ? $\endgroup$
    – user645636
    Commented Apr 15, 2019 at 19:19
  • $\begingroup$ Yes, it was a chessboard problem. $\endgroup$ Commented Apr 15, 2019 at 19:20

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ Well, not quite "all resulting summands". You have to add the ones with a $p^2$ together, and even then I'm not sure. $\endgroup$ Commented Apr 15, 2019 at 19:36
  • $\begingroup$ How do you see the next term is divisible by $p^4$ and not just $p^3$? $\endgroup$
    – Nate
    Commented Apr 15, 2019 at 19:36
  • $\begingroup$ I think your answer (once corrected a bit) perfectly complements the other :) $\endgroup$ Commented Apr 15, 2019 at 19:46
  • $\begingroup$ @darijgrinberg: Took me a while, but seems eventually correct. $\endgroup$
    – W-t-P
    Commented Apr 16, 2019 at 15:53
  • 1
    $\begingroup$ ... in $\mathbb{Z}\left[x\right]$, we have $\left(x-1\right)\left(x-2\right)\cdots\left(x-\left(p-1\right)\right) \equiv x^{p-1} - 1 \mod p$. Wilson's theorem is not required for this, but instead can be obtained as an afterthought. $\endgroup$ Commented Apr 16, 2019 at 20:06
5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$
    – Mike
    Commented Apr 15, 2019 at 20:39
  • $\begingroup$ nevermind whoops $\endgroup$
    – Mike
    Commented Apr 15, 2019 at 20:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .