We will construct the set $ B$ in $ n$ steps. In the $ k$-th step we will add an element to set $ B$ in such a way that the size of the set $ A + B$ will be at least $ kN - \frac {(k - 1)k}{2} = N + (N - 1) + (N - 2) + ... + (N - k + 1)$. We prove by induction that this is possible. For $ k = 1$ it's obvious: after adding an arbitrary residue the set $ A + B$ will have $ N$ elements. Suppose that we have already $ k - 1$ elements in the set $ B$ and the set $ A + B$ consists of $ m \geq N + (N - 1) + ... + (N - k + 2) = (k - 1)N - \frac {(k - 2)(k - 1)}{2}$ elements. Consider the sets $ B_0, B_1, ..., B_{N^2 - 1}$ where $ B_i = \{a + i: a \in A\}$. Suppose that $ l$ is minimum number such that we can't increase the size of the set $ A + B$ by $ l$. It means that every set $ B_i$ has at least $ N - l + 1$ elements in common with $ A + B$, so: $ |(A + B) \cap B_0| + |(A + B) \cap B_1| + ... + |(A + B) \cap B_{N^2 - 1}| \geq N^2(N - l + 1)$. There are $ m$ elements in the set $ A + B$ so one of them appears in this intersections at least $ \big \lceil \frac {N^2(N - l + 1)}{m} \big \rceil = s$ times. Note that $ s \leq N$. Indeed, otherwise there would be a residue with at least $ N + 1$ representations in the form $ a + i$, where $ a \in A$, but this is impossible since $ |A| = N$. So we have the inequalities: $ \frac {N^2(N - l + 1)}{m} \leq s \leq N$ so it follows that $ l \geq N + 1 - \frac {m}{N}$. Therefore \[ m + l - 1 \geq m + N - \frac {m}{N} = m\frac {N - 1}{N} + N \geq ((k - 1)N - \frac {(k - 2)(k - 1)}{2})\frac {N - 1}{N} + N = (k - 1)(N - 1) + N - (1 + 2 + ... + (k - 2))\frac {N - 1}{N} = kN - (k - 1) - (1 + 2 + ... + (k - 2))\frac {N - 1}{N} \geq kN - (k - 1) - (1 + 2 + ... + (k - 2)) = kN - \frac {(k - 1)k}{2} \] and the inductive proof is completed, because we can increase size of $ A + B$ by $ l - 1$. Hence, after the $ n$-th step the set $ A + B$ will consist of at least $ N^2 - \frac {N^2 - N}{2} = \frac {N^2 + N}{2} > \frac {N^2}{2}$ elements and the solution is finished. Note: as you can see this problem has completely nothing to do with the number theory and residues. The better way to look at this problem is as follows: Suppose that we have an $ N^2$ points regularly placed on the circle and a template, consisting of $ N$ of the given points, which we can use to paint the points of the circle (in one painting we paint $ N$ points). Prove that we can paint at least half of the given points within the $ N$ paintings.

Very very nice your solution!!! I am deeply impressed by the construction of $ \frac{N^{2}(N-l+1)}{m}\leq s\leq N$ Many thanks