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$
  • $\begingroup$ Can you give the original problem? $\endgroup$ – Phicar Apr 15 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$ – Parallelism Alert Apr 15 at 19:17
  • $\begingroup$ :P that's what i was thinking. $\endgroup$ – Phicar Apr 15 at 19:19
  • $\begingroup$ was it a chessboard problem ? $\endgroup$ – Roddy MacPhee Apr 15 at 19:19
  • $\begingroup$ Yes, it was a chessboard problem. $\endgroup$ – Parallelism Alert Apr 15 at 19:20
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$
  • 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$ – darij grinberg Apr 15 at 19:36
  • $\begingroup$ How do you see the next term is divisible by $p^4$ and not just $p^3$? $\endgroup$ – Nate Apr 15 at 19:36
  • $\begingroup$ I think your answer (once corrected a bit) perfectly complements the other :) $\endgroup$ – darij grinberg Apr 15 at 19:46
  • $\begingroup$ @darijgrinberg: Took me a while, but seems eventually correct. $\endgroup$ – W-t-P Apr 16 at 15:53
  • $\begingroup$ 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, ... $\endgroup$ – darij grinberg Apr 16 at 20:06
6
$\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$
  • $\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 Apr 15 at 20:39
  • $\begingroup$ nevermind whoops $\endgroup$ – Mike Apr 15 at 20:52

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.