# Condition that for a given set of numbers and given divisor all finite sums from this set contain all possible remainders

Given $q \in \mathbb{N}$ and ${a_1, a_2, ...}$ where each $a_j \in \mathbb{N} \cup{\{0\}}$ define $A_p=$ {set of all finite sums of $\{a_1 ... a_p\}$ such that each $a_j$ will appear either $1$ or $0$ times}. There will be $2^{p}$ elements in $A_p$. Define $R_p$ as the set of remainders of elements of $A_p$ divided by q.

What is necessary and sufficient condition for ${a_1, a_2, ...}$ such that there exist $p$ for which $\{0,1...,q-1\} = R_p$

All constraints are welcome.

## 1 Answer

SMALL number theory person here.

First of all, the problem doesn't really depend on you taking the finite subsets. We may as well just call $A = \{ \sum_{n\in\mathbb{N}} \delta_n a_n : \mbox{$\delta_n\in\{0,1\}$and all but finitely many$\delta_n$are zero}\}$ and call $R$ the set of remainders of the elements of $A$ when divided by $q$. The problem is equivalent to asking whether $R = \{0,\dots,q-1\}$.

There are a few obvious necessary conditions, such as the fact that you must have $\gcd(q,a_1,a_2,\dots) = 1$. There are also a few sufficient conditions, such as (I believe):

$\textit{If$A_q$is the set of remainders of$a_1,a_2,\dots$when divided by$q$, then$|A_q \cap \{1,\dots,q-1\}| \ge \lceil{\frac q 2}\rceil$is sufficient.}$

However, I don't think there is a nice (complete) solution to this problem. Here's why: if we let $A_q^*$ be the $\textit{multiset}$ of remainders of $a_1,a_2,\dots$ when divided by $q$, then deleting elements so that we have at most $q-1$ of each remainder, we have $|A_q^*| < q^2$. We are then asking whether (do you see why this is equivalent?), for each $0\le t\le q-1$, there is a sub-multiset of $A_q^*$ which sums to a number which is congruent to $t$ modulo $q$, and there are finitely many possibilities for such a number, as $|A_q^*| < q^2$. If you could even give an algorithm to solve this problem in polynomial time, I think you would show that the "subset sum problem" is in $P$ and be famous.

• Thank you for the answer! This is further than I got. Because of the nature of the problem I stated $A_{p}$ instead of &A\$. Unfortunately, I just found out that due to, again, nature of the problem, these all can be simplified to really easy conditions. (By using some other properties not stated here) Thanks for helping though!! – Vadim Jun 28 '16 at 21:30