EDIT: An edited and extended (Theorem 1 generalized even further, Theorem 5 extended and proved anew) version of the below solution can be found here: http://projectpen.files.wordpress.com/2009/04/pen-e16.pdf or here: http://www.cip.ifi.lmu.de/~grinberg/pene16.pdf Peter wrote: Prove that for any prime $ p$ in the interval $ \left]n, \frac {4n}{3}\right]$, $ p$ divides \[ \sum^{n}_{j = 0}{{n}\choose{j}}^{4}. \] Nice and instructive problem. Let's generalize: Theorem 1. If $ n$ and $ k$ are positive integers and $ p$ is a prime such that $ \frac {2k - 1}{2k}\left(p - 1\right) < n < p$, then $ p\mid\sum_{j = 0}^{n}\binom{n}{j}^{2k}$. Before we prove this, we first show some basic facts about binomial coefficients and remainders modulo primes. Definition. The binomial coefficient $ \binom{x}{u}$ is defined for all reals $ x$ and for all integers $ u$ as follows: $ \binom{x}{u} = \frac {x\cdot\left(x - 1\right)\cdot ...\cdot\left(x - u + 1\right)}{u!}$ if $ u$ is a positive integer, $ \binom{x}{0} = 1$, and $ \binom{x}{u} = 0$ if $ u$ is a negative integer. Theorem 2, the upper negation identity. If $ n$ is a real, and $ r$ is an integer, then $ \binom{ - n}{r} = \left( - 1\right)^{r}\binom{n + r - 1}{r}$. Proof of Theorem 2. We will only consider the case of $ r$ being positive (the other cases are trivial). Then, using the definition of binomial coefficients, $ \binom{ - n}{r} = \frac {\left( - n\right)\cdot\left( - n - 1\right)\cdot ...\cdot\left( - n - r + 1\right)}{r!} = \left( - 1\right)^{r}\cdot\frac {n\cdot\left(n + 1\right)\cdot ...\cdot\left(n + r - 1\right)}{r!}$ $ = \left( - 1\right)^{r}\cdot\frac {\left(n + r - 1\right)\cdot ...\cdot\left(n + 1\right)\cdot n}{r!} = \left( - 1\right)^{r}\cdot\binom{n + r - 1}{r}$. This proves Theorem 2. Theorem 3. If $ p$ is a prime, if $ u$ and $ v$ are two integers such that $ u\equiv v\mod p$, and if $ k$ is an integer such that $ k < p$, then $ \binom{u}{k}\equiv\binom{v}{k}\mod p$. Proof of Theorem 3. If $ k\leq 0$, then $ \binom{u}{k} = \binom{v}{k}$, so that Theorem 3 is trivial. Thus, it remains to consider the case $ k > 0$ only. In this case, $ k!$ is coprime with $ p$ (since $ k! = 1\cdot 2\cdot ...\cdot k$, and all numbers $ 1$, $ 2$, ..., $ k$ are coprime with $ p$, since $ p$ is a prime and $ k < p$). Now, $ u\equiv v\mod p$ yields $ k!\cdot\binom{u}{k} = k!\cdot\frac {u\cdot\left(u - 1\right)\cdot ...\cdot\left(u - k + 1\right)}{k!} = u\cdot\left(u - 1\right)\cdot ...\cdot\left(u - k + 1\right)$ $ \equiv v\cdot\left(v - 1\right)\cdot ...\cdot\left(v - k + 1\right) = k!\cdot\frac {v\cdot\left(v - 1\right)\cdot ...\cdot\left(v - k + 1\right)}{k!}$ $ = k!\cdot\binom{v}{k}\mod p$. Since $ k!$ is coprime with $ p$, we can divide this congruence by $ k!$, and thus we get $ \binom{u}{k}\equiv\binom{v}{k}\mod p$. Hence, Theorem 3 is proven. Finally, a basic property of binomial coefficients: Theorem 4. For every nonnegative integer $ n$ and any integer $ k$, we have $ \binom{n}{k} = \binom{n}{n - k}$. This is known, but it is important not to forget the condition that $ n$ is nonnegative (it is necessary!). Now to something completely different: Theorem 5. If $ p$ is a prime, and $ f$ is a polynomial of degree $ < p - 1$ whose coefficients are all integers, then $ \sum_{j = 0}^{p - 1}f\left(j\right)\equiv 0\mod p$. Proof of Theorem 5. Since $ f$ is a polynomial of degree $ < p - 1$ whose coefficients are all integers, it can be written in the form $ f\left(X\right) = \sum_{i = 0}^{p - 2}f_{i}X^{i}$ with $ f_{i}$ being an integer (not necessarily nonzero) for every $ i\in\left\{0;\;1;\;...;\;p - 3;\;p - 2\right\}$. Hence, $ \sum_{j = 0}^{p - 1}f\left(j\right) = \sum_{j = 0}^{p - 1}\sum_{i = 0}^{p - 2}f_{i}j^{i} = \sum_{i = 0}^{p - 2}f_{i}\cdot\sum_{j = 0}^{p - 1}j^{i}$. But for every $ i\in\left\{0;\;1;\;...;\;p - 3;\;p - 2\right\}$, we have $ \sum_{j = 0}^{p - 1}j^{i}\equiv 0\mod p$ (in fact, for $ i = 0$, this is clear since $ \sum_{j = 0}^{p - 1}j^{0} = \sum_{j = 0}^{p - 1}1 = p$, and for $ i\geq 1$, this is equivalent to $ \sum_{j = 1}^{p}j^{i}\equiv 0\mod p$ (since $ \sum_{j = 0}^{p - 1}j^{i}\equiv \sum_{j = 1}^{p}j^{i}\mod p$, because $ 0^{i}\equiv p^{i}\mod p$), what follows from http://www.problem-solving.be/pen/viewtopic.php?t=676 part a) because $ p - 1\nmid i$). Thus, $ \sum_{j = 0}^{p - 1}f\left(j\right) = \sum_{i = 0}^{p - 2}f_{i}\cdot\sum_{j = 0}^{p - 1}j^{i}\equiv\sum_{i = 0}^{p - 2}f_{i}\cdot 0 = 0\mod p$, and Theorem 5 is proven. Proof of Theorem 1. We have $ p - n - 1\geq 0$, since $ n < p$ yields $ n + 1\leq p$. Also, $ \frac {2k - 1}{2k}\left(p - 1\right) < n$ yields $ \left(2k - 1\right)\left(p - 1\right) < 2kn$, so that $ 2k\left(p - 1\right) - \left(p - 1\right) < 2kn$, thus $ 2k\left(p - 1\right) - 2kn < p - 1$, or, equivalently, $ 2k\left(p - n - 1\right) < p - 1$. We have to prove that $ p\mid\sum_{j = 0}^{n}\binom{n}{j}^{2k}$. This rewrites as $ \sum_{j = 0}^{n}\binom{n}{j}^{2k}\equiv 0\mod p$. This is equivalent to $ \sum_{j = 0}^{p - 1}\binom{n}{j}^{2k}\equiv 0\mod p$ (in fact, since $ n < p$, the two sums $ \sum_{j = 0}^{p - 1}\binom{n}{j}^{2k}$ and $ \sum_{j = 0}^{n}\binom{n}{j}^{2k}$ differ only in some terms $ \binom{n}{j}^{2k}$ with indices $ j$ in the interval $ \left]n;\;p - 1\right]$, and these terms are zero, so we have $ \sum_{j = 0}^{p - 1}\binom{n}{j}^{2k} = \sum_{j = 0}^{n}\binom{n}{j}^{2k}$). For every integer $ j$ with $ 0\leq j < p$, we have $ \binom{n}{j} = \binom{ - \left( - n\right)}{j} = \left( - 1\right)^{j}\binom{\left( - n\right) + j - 1}{j}$ (after Theorem 2) $ \equiv\left( - 1\right)^{j}\binom{p - n + j - 1}{j}$ (by Theorem 3, since $ \left( - n\right) + j - 1\equiv p - n + j - 1\mod p$ and $ j < p$) $ = \left( - 1\right)^{j}\binom{p - n + j - 1}{\left(p - n + j - 1\right) - j}$ (by Theorem 4, since $ p - n + j - 1$ is nonnegative, since $ p - n - 1\geq 0$ and $ j\geq 0$) $ = \left( - 1\right)^{j}\binom{p - n + j - 1}{p - n - 1}\mod p$, so that $ \binom{n}{j}^{2k}\equiv\left(\left( - 1\right)^{j}\binom{p - n + j - 1}{p - n - 1}\right)^{2k} = \binom{p - n + j - 1}{p - n - 1}^{2k}\mod p$ (since $ 2k$ is even). Therefore, (1) $ \left(p - n - 1\right)!^{2k}\cdot\sum_{j = 0}^{p - 1}\binom{n}{j}^{2k}\equiv\left(p - n - 1\right)!^{2k}\cdot\sum_{j = 0}^{p - 1}\binom{p - n + j - 1}{p - n - 1}^{2k}$ $ = \sum_{j = 0}^{p - 1}\left(\left(p - n - 1\right)!\cdot\binom{p - n + j - 1}{p - n - 1}\right)^{2k}$ $ = \sum_{j = 0}^{p - 1}\left(\left(p - n - 1\right)!\cdot\frac {\prod_{u = 0}^{\left(p - n - 1\right) - 1}\left(\left(p - n + j - 1\right) - u\right)}{\left(p - n - 1\right)!}\right)^{2k}$ $ = \sum_{j = 0}^{p - 1}\left(\prod_{u = 0}^{\left(p - n - 1\right) - 1}\left(\left(p - n + j - 1\right) - u\right)\right)^{2k}\mod p$. Now, $ \prod_{u = 0}^{\left(p - n - 1\right) - 1}\left(\left(p - n + X - 1\right) - u\right)$ is a polynomial of the variable $ X$ whose degree is $ p - n - 1$. Thus, $ \left(\prod_{u = 0}^{\left(p - n - 1\right) - 1}\left(\left(p - n + X - 1\right) - u\right)\right)^{2k}$ is a polynomial of the variable $ X$ whose degree is $ 2k\left(p - n - 1\right)$. Since $ 2k\left(p - n - 1\right) < p - 1$, it is therefore a polynomial of degree $ < p - 1$. Since the coefficients of this polynomial are all integers, Theorem 5 thus yields $ \sum_{j = 0}^{p - 1}\left(\prod_{u = 0}^{\left(p - n - 1\right) - 1}\left(\left(p - n + j - 1\right) - u\right)\right)^{2k}\equiv 0\mod p$. Using (1), this becomes $ \left(p - n - 1\right)!^{2k}\cdot\sum_{j = 0}^{p - 1}\binom{n}{j}^{2k}\equiv 0\mod p$. Now, $ \left(p - n - 1\right)!$ is coprime with $ p$ (since $ \left(p - n - 1\right)! = 1\cdot 2\cdot ...\cdot\left(p - n - 1\right)$, and all numbers $ 1$, $ 2$, ..., $ p - n - 1$ are coprime with $ p$ because $ p$ is a prime and $ p - n - 1 < p$). Hence, we can divide this congruence by $ \left(p - n - 1\right)!^{2k}$, and obtain $ \sum_{j = 0}^{p - 1}\binom{n}{j}^{2k}\equiv 0\mod p$. As we said, this proves Theorem 1. Darij