Given $p - 1$ integers not divisible by an odd prime $p$, we can change signs of some (all or none) of them so that their sum is divisible by $p$.

Question

I'm currently trying to solve this problems, but ran out of ideas. In my textbook this problem goes after a series of problems related to variations of this zero-sum problem, but it may or may not be related to them. I tried thinking about reducing the problem to the previously mentioned one by somehow extending the set of $p - 1$ numbers to $2p - 1$ numbers or trying to come up with something related to applying pigeonhole on subsets of $p - 1$ numbers. I've checked this statement with a program for small numbers, and it seems to be true, and $p$ being prime is also important. Code for those interested, though it's irrelevant to the question.

Any help is appreciated.

Answer 1

Outline of proof:

• The Cauchy–Davenport theorem says that given two subsets $A,B$ of $\Bbb Z/p\Bbb Z$, the number of residue classes modulo $p$ that can be written as $a+b$ where $a\in A,b\in B$ (in other words, $\#(A+B)$) is at least $\min\{p,\#A+\#B-1\}$. (This theorem isn't hard to prove by induction on $\#B$, and the primeness of $p$ is definitely used.)
• A simple induction then establishes the many-set version: $\#(A_1+\dots+A_k) \ge \min\{p,\#A_1+\cdots+\#A_k-(k-1)\}$.
• If $S=\{a_1,\dots,a_k\}$ is a set of integers none of which is divisible by $p$, then taking $A_j=\{0,a_j\}$ yields the inequality $\#\Sigma S \ge \min\{p,k+1\}$, where $\Sigma S$ denotes the set of sums of all subsets of $S$. In particular, when $k=p-1$, every residue class modulo $p$ can be written as a sum of some subset of $S$ (possibly $\emptyset$ and possibly $S$ itself).
• For the problem in the OP, given a set $S$ of $p-1$ integers not divisible by $p$, let $m$ be the sum of all elements modulo $p$. Find a subset $T$ of $S$ such that the sum of the elements of $T$ is congruent to $2^{-1}m = \frac{p+1}2m$ modulo $p$. Then changing the signs of all the elements of $T$ results in the new sum of the elements of modified-$S$ being a multiple of $p$.