MathLabs

Problem 3

Let p≥5p\ge5 be a prime. Let rr be the number of ways of placing pp identical checkers on a p×pp\times p checkerboard so that not all checkers are in the same row (they may all be in the same column). Show that rr is divisible by p5p^5.
Step 2 of 5: Introduce the coefficient polynomial
Previous stepNext step
f(x)=∏i=1p−1(x−i)=xp−1+sp−2xp−2+⋯+s1x+s0f(x)=\prod_{i=1}^{p-1}(x-i)=x^{p-1}+s_{p-2}x^{p-2}+\cdots+s_1x+s_0
Detailed analysis

Set f(x)=∏i=1p−1(x−i)=xp−1+sp−2xp−2+⋯+s1x+s0f(x)=\prod_{i=1}^{p-1}(x-i)=x^{p-1}+s_{p-2}x^{p-2}+\cdots+s_1x+s_0. Fermat's theorem gives xp−1−1≡f(x)(modp)x^{p-1}-1\equiv f(x)\pmod p. Comparing coefficients yields p∣sip\mid s_i for 1≤i≤p−21\le i\le p-2 and s0≡−1(modp)s_0\equiv-1\pmod p.