Proving that this sum $\sum\limits_{0 < k < \frac{2p}{3}} { p \choose k}$ is divisible by $p^{2}$

How does one prove that for a prime $p \geq 5$ the sum : $$\sum\limits_{0 < k < \frac{2p}{3}} { p \choose k}$$ is divisible by $p^{2}$.

Since each term of $\displaystyle \sum\limits_{0 < k < \frac{2p}{3}} { p \choose k}$ is divisible by $p$, only thing remains is to prove that the sum $$\sum\limits_{ 0 < k < \frac{2p}{3}} \frac{1}{p} { p \choose k}$$ is divisible by $p$.

How to evaluate this sum: $\displaystyle \frac{1}{p} { p \choose k} = \frac{(p-1)(p-2) \cdots (p-k+1)}{1 \cdot 2 \cdot 3 \cdots k}$

Solution 1:

Since we are working in the field $\mathbb{F}_p$ we can write

$$\frac{(p-1)(p-2) \cdots (p-k+1)}{1 \cdot 2 \cdots k}$$ as

$$\frac{(-1)(-2) \cdots (-(k-1))}{1 \cdot2 \cdots k}$$

= $$\frac{(-1)^{k-1}}{k}$$

Let $N = [\frac{2p}{3}]$ and $M = [\frac{N}{2}]$

Thus what we need is

$$ \sum_{k=1}^{N} \frac{(-1)^{k-1}}{k}$$ $$ = \sum_{k=1}^{N} \frac{1}{k} - 2 \sum_{k=1}^{M}\frac{1}{2k}$$ $$ =\sum_{k=M+1}^{N}\frac{1}{k}$$

Now $N+M+1 =p$ so we can rewrite as

$$\frac{1}{N} + \frac{1}{M+1} + \frac{1}{N-1} + \frac{1}{M+2} + \cdots = $$

$$\frac{p}{N(M+1)} + \frac{p}{(N-1)(M+2)} + \cdots $$

which is $0$.

There are $N-M$ terms, which is even, so each term gets paired off.

Solution 2:

From your last equation one gets $$\frac1p{p\choose k}\equiv(-1)^k\frac 1k\pmod p.$$ So the problem is equivalent to $$\sum_{0 < k < 2p/3}(-1)^k\frac1k\equiv0\pmod{p}.$$

The case $p=1979$ was set as the first problem at the 1979 IMO. The method used for this extends to all primes, and no doubt you can find solutions for the IMO problem out on the interweb.