For any $n-1$ non-zero elements of $\mathbb Z/n\mathbb Z$, we can make zero using $+,-$ if and only if $n$ is prime

Question

Inspired by Just using $+$ ,$-$, $\times$ using any given n-1 integers, can we make a number divisible by n?, I wanted to first try to answer a simpler version of the problem, that considers only two operations instead of three.

---

Let $n>2$ and parentheses are not allowed. Then, there are equivalent ways to ask this:

• Given any set of $n-1$ non-multiples of $n$, can we make a multiple of $n$ using $+,-$?

• Given any $n-1$ non-zero elements of $\mathbb Z/n\mathbb Z$, can we make $0$ using $+,-$?

Alternatively, we can also be asking to partition a $n-1$ element set $S$ into two subsets $S_+$ and $S_-$, such that the difference between the sum of elements in $S_+$ and the sum of elements in $S_-$ is a multiple of $n$ (is equal to $0$ modulo $n$).

For example, if $n=3$ then there are only $3$ (multi)sets we need to consider:

$$ \begin{array}{} 1-1=0\\ 1+2=0\\ 2-2=0\\ \end{array} $$

which are all solvable (we can make a $0$ in $\mathbb Z/n\mathbb Z$).

In general, there are $\binom{2n-3}{n-1}$ (multi)sets to consider for a given $n$.

---

My conjecture is that any such (multi)set is solvable if and only if $n$ is a prime number.

If $n$ is not prime, then it is not hard to see that this cannot be done for all (multi)sets. If $n$ is even, then take all $n-1$ elements to equal $1$, to build an unsolvable (multi)set. If $n$ is odd, then take $n-2$ elements to equal to a prime factor of $n$ and last element to equal to $1$, to build an unsolvable (multi)set.

It remains to show that if $n$ is prime, then all such (multi)sets are solvable.

I have confirmed this for $n=3, 5, 7, 11, 13$ using a naive brute force search.

Can we prove this conjecture? Or, can we find a prime that does not work?

Answer 1

Number the elements of the set $k_1, k_2, \dots, k_{p-1}$, where $p$ is an odd prime.

Another equivalent way to ask the question is to phrase it in terms of sum sets, where $A+B$ is defined to be $\{a + b : a \in A, b \in B\}$. The possible ways to specify the signs in $\pm k_1 \pm k_2 \pm \dots \pm k_{p-1}$ are the elements of the sum set $$ \{k_1, -k_1\} + \{k_2, -k_2\} + \{k_3, -k_3\} + \dots + \{k_{p-1}, -k_{p-1}\}. $$ Allowing $k_1$ to be negative is fine, since if we get $0$ with a negative $k_1$, we can flip every sign and get $0$ with a positive $k_1$.

By the Cauchy-Davenport theorem, when working in $\mathbb Z / p \mathbb Z$ for any prime $p$, we have $$|A+B| \ge \min\{|A|+|B|-1, p\}.$$ When $p$ is an odd prime and $x$ is not a multiple of $p$, $\{x, -x\}$ has size $2$, so by iterating the theorem with the sum set above, we have:

• $|\{k_1, -k_1\} + \{k_2, -k_2\}| \ge 2 + 2 - 1 = 3$.
• $|\{k_1, -k_1\} + \{k_2, -k_2\} + \{k_3, -k_3\}| \ge 3 + 2 - 1 = 4$.
• $|\{k_1, -k_1\} + \{k_2, -k_2\} + \{k_3, -k_3\} + \{k_4, -k_4\}| \ge 4 + 2 - 1 = 5$.
• ...
• $|\{k_1, -k_1\} + \{k_2, -k_2\} + \{k_3, -k_3\} + \dots + \{k_{p-1}, -k_{p-1}\}| \ge p$.

So all $p$ values are possible; in particular, $0$ is possible.