Problem 3

Let

p\ge5

be a prime. Let

r

be the number of ways of placing

p

identical checkers on a

p\times p

checkerboard so that not all checkers are in the same row (they may all be in the same column). Show that

r

is divisible by

p^5

Step 4 of 5: Obtain the required product congruence

Previous step Next step

f(p^2)-s_0=s_1p^2+\cdots\equiv0\pmod{p^4}

Detailed analysis

Expanding $f(p^2)-s_0$ gives $s_1p^2+s_2p^4+\cdots$ . Since $p^2\mid s_1$ , the first term is divisible by $p^4$ , and every later term is also divisible by $p^4$ . Therefore $f(p^2)-s_0\equiv0\pmod{p^4}$ , exactly the congruence needed in Step 1.