It maybe a hard problem.But when you compare this problem to the famous(Lemma 1),you will have a approach to combine them.The nice ideas you must pairs the residue of $n$ when $(m,n)>1$. The answer is $N_{min}=\max\{m,n-\frac{(m,n)-1}{2}\cdot m\}.$Where $(m,n)$ is the greatest common divsor of integer $m$ and $n$. Lemma 1:For any positive integer $n$,and any integers $a_1,a_2,\cdots,a_n$,then there exist an nonempty set $I$ of $\{1,2,\cdots,n\}$,such that $n| {\sum\limits_{i \in I} a_i } $ Lemma 2:For any positive even integer $n$,and any integers $a_1,a_2,\cdots,a_{n/2+1}$ and$a_1 \equiv \frac{n}{2}\pmod{n}$.then there exist an nonempty set $I$ of $\{1,2,\cdots,1+\frac{n}{2}\}$,such that $n| {\sum\limits_{i \in I} a_i } $(Proof of Lemma 1 and 2 is left for you.) Back to the orginal problem.Suppose $(m,n)=d,m=m_1d,n=n_1d$. (a)$d$ is an odd integer, (i)when $m\ge n-\frac{(m,n)-1}{2}\cdot m$,we shall prove for any set $S$ contains a complete residue system of $m$,then there exit a nonempty set $A \subseteq S$, that $n| {\sum\limits_{x \in A} x } $.Let's do this.Suppose $a_{ij}\in S(i=1,2,\cdots,d;j=1,2,\cdots,m_1)$ such that \[a_{ij}\equiv i \pmod{d},i=1,2,\cdots,d;j=1,2,\cdots,m_1.\] then we have \[b_1=a_{11}+a_{d-1,1},b_2=a_{12}+a_{d-1,2},\cdots,b_{m_1}=a_{1m_1}+a_{d-1,m_1};\] \[b_{m_1+1}=a_{21}+a_{d-2,1},b_{m_1+2}=a_{22}+a_{d-2,2},\cdots,b_{2m_1}=a_{2m_1}+a_{d-2,m_1};\] \[\cdots\] \[b_{\frac{d-3}{2}m_1+1}=a_{\frac{d-1}{2},1}+a_{\frac{d+1}{2},1},b_{\frac{d-3}{2}m_1+2}=a_{\frac{d-1}{2},2}+a_{\frac{d+1}{2},2},\] \[\cdots,b_{\frac{d-1}{2}m_1}=a_{\frac{d-1}{2},m_1}+a_{\frac{d+1}{2},m_1}\] \[b_{\frac{d-1}{2}m_1+1}=a_{d1},b_{\frac{d-1}{2}m_1+2}=a_{d2},\cdots,b_{\frac{d+1}{2}m_1}=a_{dm_1}.\] Because $b_1,b_2,\cdots,b_{\frac{d+1}{2}m_1}$ are all multiplies of $d$,we can set $b_i=dk_i,i=1,2,\cdots,\frac{d+1}{2}m_1$,and with $m\ge n-\frac{(m,n)-1}{2}\cdot m \iff \frac{d+1}{2}m_1 \ge n_1$. By Lemma 1 we can find and nonempty subset $I$ of $\{1,2,\cdots,\frac{d+1}{2}m_1\}$,such that,$n_1| \sum_{i\in I} k_i$,which means $n| \sum_{i\in I}b_i$.Which complete the solution in this case. (ii)when $m< n-\frac{(m,n)-1}{2}\cdot m$,then when $N=n-\frac{(m,n)-1}{2}\cdot m$.Set $a_{ij},b_i$ and $k_i$ as in case (i),let $S_1=S\setminus \{a_{ij}\}$.And in this case there left at least $n-\frac{(m,n)+1}{2}\cdot m=d(n_1-\frac{d+1}{2}m_1)$ in $S_1$,by Lemma 1 some times we can prove there exist nonempty subsets $A_1,A_2,\cdots,A_{n_1-\frac{d+1}{2}m_1}$(with empty intersection) of $S_1$ such that $b_{\frac{d+1}{2}m_1+j}=\sum_{a\in A_j},j=1,2,\cdots,n_1-\frac{d+1}{2}m_1$ are all multiplies of $d$.Set $c_j=dk_{j},j=\frac{d+1}{2}m_1+1,\frac{d+1}{2}m_1+2,\cdots,n_1$.Again by Lemma 1,we can find and nonempty subset $I$ of $\{1,2,\cdots,n_1\}$,such that,$n_1| \sum_{i\in I} k_i$,which means $n| \sum_{i\in I}b_i$,which means we can find a nonempty set $A$ of $S$ such that $n|\sum_{x\in A} x$. And for $N=n-\frac{(m,n)-1}{2}\cdot m-1$,let $S$ consists of $i\cdot n+j,i=1,2,\cdots,m_1;j=1,2,\cdots,d$,and the other $a \in S$ such that $a\equiv 1 \pmod{n}$.Then $S$ is an example. (b)$d$ is an even integer.I'm tired to write solution in this case,In this case the $a_{ij}$ may can't be pairs,we can use Lemma 2 in somewhere to complete the solution.

Could you explain what is this: $a_{ij}\equiv i,i=1,2,\cdots,d;j=1,2,\cdots,m_1.$ Seems it is not a complete residue system module $m$.

i understand that $ a_{ij}\equiv i (mod d) $ and $ a_{ij}\equiv j (mod m_1) $, but we don't have $ (d,m_1)=1 $, so i think we can't find all of them. does anybody have the solution for this problem?

Nazar_Serdyuk wrote: Could you explain what is this: $a_{ij}\equiv i,i=1,2,\cdots,d;j=1,2,\cdots,m_1.$ Seems it is not a complete residue system module $m$. I missed the "$\pmod{d}$".Because $S$ has a complete residue system module $m$,then we can choose such $a_{ij}$. To malilim,I don't what is your question.We don't need $(d,m_1)=1$ anywhere.

Hey guys, why isn't the answer $N=1$? If $N=1$, then there does not exist any complete residue system mod $m$ with $|S|=1$, so there is no need to prove the implication.

johnmichaelwu wrote: Hey guys, why isn't the answer $N=1$? If $N=1$, then there does not exist any complete residue system mod $m$ with $|S|=1$, so there is no need to prove the implication. I think the problem statement should be interpreted as $|S|\geq N$, otherwise we can just pick $N=1$. For a set $A$ let $S(A)$ be its sum of digits We now solve the problem Let $d=(m,n)$ and $m=ad$, $n=bd$. The answer is $$\begin{cases}1& \text{ if }bd\leq \frac{ad(d+1)}{2}\\bd-\frac{ad(d-1)}{2}&\text{ otherwise}\end{cases}$$Lemma. (i) If $S=\{a_1,...,a_{n}\}$ is a set of positive integers then there exists nonempty $A\subset S$ such that $n|S(A)$. (ii) If $n$ is even, and $|S|=\frac{n}{2}$ then there exists nonempty $A\subset S$ such that $n|S(A)$ or $n|S(A)-\frac{n}{2}$ Proof. Let $$b_i=\sum_{k=1}^ia_k$$If $b_i\equiv 0\pmod n$ for some $i$ then we are done. Otherwise by pigeonhole principle there exists $1\leq i\leq j\leq n$ such that $b_i\equiv b_j\pmod n$, hence $$a_{i+1}+...+a_j\equiv 0\pmod n$$as desired. $\blacksquare$ By Chinese Remainder Theorem, the condition of containing the entire residue system is equivalent to the assertion that for each $i$ the set $S$ contains at least a elements which is $i\pmod d$, we will denote them by $b_i^1,b_i^2,...,b_i^a$. Now we consider the two cases. If $bd\geq \frac{ad(d+1)}{2}$, we show that there always exists $A\subset S$ such that $n|S(A)$ regardless of the size of $S$. Indeed, consider the numbers $$b_i^j+b_{d-i}^j$$where $i=1,2,...,n-1\setminus\{\frac{n}{2}\}$ and $b_d^1,...,b_d^a$, it is easy to see that there are at least $b$ numbers and each of them is divisible by $d$, hence we are done applying the lemma. For the other case, we can choose for each of the residue classes $1,...,d$ modulo $abd$, $a$ numbers. Meanwhile, we pick $$bd-\frac{ad(d+1)}{2}-1$$numbers congruent to $1$ modulo $abd$, then $$\frac{ad(d+1)}{2}+bd-\frac{ad(d+1)}{2}-1$$will be less than $bd$ hence no subset $A$ exists. Now if $|S|\geq bd-\frac{ad(d-1)}{2}$ by the lemma and a similar method in the above case we can pick $b$ pairwise disjoint sets whose sum of elements are all divisible by $d$ so we are done.

Lemma: if I have n integers, a nonempty subset of them is divisible by n. Proof: Assume not. Consider $x_1, x_1+x_2, \cdots, x_1+\cdots+x_n$. If all of them are nonzero, two of them are congruent mod $n$ since they can take on n-1 nonzero values. Their difference works. Let $d=\gcd(m,n)$ and $k=\frac md$. It's best to think of a complete residue system mod m as k systems mod d because we only care about numbers mod n, which is in gaps of size d. Claim: if d is odd, then the answer is $m$ if $k\frac{d+1}{2}\ge \frac nd$ and $m+(n-kd\frac{d+1}{2})$ otherwise If $k\frac{d+1}{2}\ge \frac nd$ then I can break each of the k complete residues mod d into $k\frac{d+1}{2}$ groups of 1 or 2 elements whose sum is divisible by d. The grouping is like this: d, (1,d-1), (2,d-2), ..., $(\frac{d-1}{2}, \frac{d+1}{2})$ If I take these $k\frac{d+1}{2}$ groups and divide each by $d$, I have $k\frac{d+1}{2}$ integers waiting to be divisible by $\frac nd$. By our lemma we proved $m$ elements are sufficient. Their necessity is obvious. If $k\frac{d+1}{2}< \frac nd$, there are $k\frac{d+1}{2}$ groups with sum divisible by $d$. If I have another $n-kd\frac{d+1}{2}$ numbers, there exist at least $\frac nd - k\frac{d+1}{2}$ sets that are multiples of $d$, and combining we have $\frac nd$ groups of multiples of $d$, which guarantees a multiple of $n$. Construction: I can use multisets since I can increment elements by $mn$ freely. A construction is $k$ copies of $\{1,\cdots,d\}$ (in the end they form the complete residue system mod $m$) and another $n-k\frac{d(d+1)}{2}-1$ 1's. The sum of these elements is $n-1$ and all elements are positive, so at least $m+n-k\frac{d(d+1)}{2}$ elements are needed. If $d$ is even then the answer is still the same, except for I may need to address groups of $\frac d2$ numbers to form another group divisible by $d$.

Solved with Cookierookie and sevket12.