# Is $\sum\limits^n_{k=0}\frac{(y-0)(y-1)\cdots(y-n)}{y-k} \equiv 0 \pmod{n+1}$?

Let $n$ be a positive integer such that $n+1$ is a prime power. That is, to illustrate $n+1$ is $9$ or $25$. Prove that

$$\sum^n_{k=0}\frac{(y-0)(y-1)\cdots(y-n)}{y-k} \equiv 0 \pmod{n+1}.$$

Hint: I think every summand is zero modulo $n+1$.

-
It's not true that every summand is 0 mod n+1. Take n+1 prime, y=n+1,k=0 –  user64480 Apr 27 '13 at 16:01
Certainly if the summands are to be interpreted as polynomials in the indeterminate $y$, then they are very nonzero. –  Erick Wong Apr 27 '13 at 16:03
Good point. Is y an indeterminate or an integer? –  user64480 Apr 27 '13 at 16:05
Something seems wrong. If you take n+1 to be prime, and y=0, then the k=0 term doesn't vanish, whereas the other terms do vanish. So the sum doesn't vanish. –  user64480 Apr 27 '13 at 16:14
With $n=2$, the claim is about $(y-1)(y-2)+(y-0)(y-2)+(y-0)(y-1) = 3y^2-6y+2\equiv -1\pmod 3$. –  Hagen von Eitzen Apr 27 '13 at 16:18

The sum is symmetric in $y \pmod{n+1}$, so we may assume without loss that $y=n+1$, in which case the sum becomes $\frac{(n+1)!}{1}+\frac{(n+1)!}{2}+\frac{(n+1)!}{3}+\cdots +\frac{(n+1)!}{n+1}$. All of these terms are $0$ mod $n+1$ except possibly the last, $n!$. Suppose $n+1=k^2$, with $k> 2$. Then $k$ and $2k$ each divide $n!$, hence $(n+1)|(2k)k|n!$. I leave the cases $n+1=4,1$ for you to consider.

-

Let $n+1 = p^r$

Define $$Y_n = \sum_{k=0}^n \prod_{\substack{i=0 \\ i\not = k}}^n(y-i)$$

First prove for $y=0$ by noting $$Y_n \equiv \prod_{i=1}^n(y-i)$$ and this $\equiv 0$ since it's a product of $p^r-1$ consecutive terms, therefore it is divisible by $p^r$.

The result follows for all $y$ since the expression is translation invariant

-