Let p be a prime ≥ 5. Prove that p^{2} divides ∑_{0}^{[2p/3]} pCr.

**Solution**

*Straightforward, provided you work in the field mod p.*

Obviously each pCi is divisible by p. So we have to show that S = pC1/p + pC2/p + ... + pCk/p is divisible by p. We work in the field mod p. pCi/p = (p-1)...(p-i)/(1.2. ... i) = (-1)^{i-1}1/i. Hence S = 1 - 1/2 + ... +/- 1/k = 1 + 1/2 + ... + 1/k - 2(1/2 + 1/4 + ... + 1/2h) = 1 + 1/2 + ... + 1/k - (1 + 1/2 + ... + 1/h) = 1 + 1/2 + ... + 1/k + (1/(p-1) + 1/(p-2) + ... + 1/(p-h) ). By considering p = 1, 2 (mod 3) separately, we can easily check that p-h = k+1 and hence S = 1 + 1/2 + ... + 1/(p-1), which is a complete set of reduced residues and hence sums to zero.

© John Scholes

jscholes@kalva.demon.co.uk

12 Dec 1998