Question

Show that if p is a prime number, and k is an integer\[ 2 \le k \le p\], then the sum of the products of each k-element subset of\[ \{1, 2, \ldots, p\}\] is divisible by p.

Answer 1

Wouldn't this also be true for \(k=1\) since \(1+2+3+...+p≡0 \mod p\)? That is unless \(p=2\).

Answer 2

How about rewriting \(\{1, 2, ..., p\}\) as \[S=\{1, 2, ..., \frac{p-1}{2}, -\frac{p-1}{2}, ..., -1, 0\}\]So any term in our sum of products that includes \(0\) is automatically divisible by \(p\). So we just need to show that for \(2\leq k\leq p-1\) the proposition holds for the set \(S\).

I still can't tell if rewriting the set that way helps us or not though.

Answer 3

Hint:
Factor
\[
x^p -x \text { in } Z_p
\]

Answer 4

Well let's see here. \(x^p-x=((x-1)(x-2)(x-3)...(x-(p-1))(x-p)\in\mathbb{Z}_p\)
In this expression, we have every product of \(k\)-element subsets of \(\{1, 2, ..., p\}\) multiplied by some negative 1's.

Answer 5

If we write this a different way, we get \[x^p-x^{p-1}(1+2+...+p)+x^2(1\cdot2+1\cdot3+...+(p-1)\cdot p)-x^{p-3}(...)+...-p!\]

Answer 6

That should be \[x^p-x^{p-1}(1+2+...+p)+x^{p-2}(1\cdot2+1\cdot3+...+(p-1)\cdot p)-x^{p-3}(...)+...-p!\]

Answer 7

If we set this equal to \(x^p-x\), we have that every term should be 0 mod p except for the last one with a factor of x. So every term is divisible by p except for the term that has the sum of products of \(p-1\) element subsets.

In short, this proves it for \(2\leq k <p-1\) and \(k=p\). We're only missing \(k=p-1\).

Answer 8

However, shouldn't that term be \(-1 \mod p\) by Wilson's Theorem? All the products in that sum have a factor of \(p\) except for the \((p-1)!\equiv -1\mod p\).

Answer 9

I'm thinking that for \(k=p-1\), it should be \(-1\mod p\) since you have \[\frac{p!}{p}+\frac{p!}{p-1}+\frac{p!}{p-2}+...+\frac{p!}{2}+\frac{p!}{1} \mod p\]\[\equiv (p-1)!+p(\text{stuff}) \equiv -1+0\equiv-1\mod p\]

Answer 10

For example. Let \(p=3\) and \(k=p-1=2\). Then we're summing \[1\cdot2+1\cdot3+2\cdot3=11\equiv 2\equiv-1 \mod p\]