How to show that $\sum \limits_{ \{x_1,x_2, \cdots , x_k \} \in S} \prod\limits_{i=1}^{k} x_i \equiv 0\ (\text {mod}\ p).$

Question

Let $p$ be an odd prime. For each $1 \leq k \leq p-2$ consider the sets $S$ of all $k$-subsets of $\{1,2, \cdots, p-1 \}.$ Show that $$\sum \limits_{ \{x_1,x_2, \cdots , x_k \} \in S} \prod\limits_{i=1}^{k} x_i \equiv 0\ (\text {mod}\ p).$$

It is easy to prove this result for $k=1.$ But I can't proceed to prove this result for any $k>1.$ How to show that? Any help will be highly appreciated.

Thank you very much.

Answer 1

Consider the polynomial $$F(X)=(X+1)(X+2)\cdots(X+p-1).$$ Then $$F(X)=X^{p-1}+\sum_{k=1}^{p-1}S_kX^{p-1-k}$$ where $S_k$ is your sum.

But over the field $\Bbb F_p=\Bbb Z/p\Bbb Z$ I claim that $f(X)=X^{p-1}-1$. This is because each of $-1$, $-2,\ldots,-(p-1)$ solve $X^{p-1}-1\equiv 0\pmod p$ (Fermat's little theorem), so that each of $X+1,\ldots,X+p-1$ is a factor of $X^{p-1}-1$ over $\Bbb F_p$. Thus over $\Bbb F_p$, $F(X)=X^{p-1}-1$.

This means that $S_k\equiv0\pmod p$ for $1\le k\le p-2$ (and that $S_{p-1}=(p-1)!\equiv-1\pmod p$ (Wilson's theorem)).