Max number of elements from $\{1,2,\ldots, 2015\}$ such that any two elements satisfy $a-b \nmid a+b.$ 
Let $S$ be a subset of the set $\{ 1, 2, 3, \ldots , 2015\}$ such that for any two distinct elements $a$, $b$ in $S$, $a-b \nmid a+b$. Find the maximum number of elements in $S$.

I found a construction for $672$ total elements, which is taking everything that is $2 \text{ mod } 3$ which gives $671$, and then adding $1$ to $S$. However, I am not sure how to prove this construction is maximal. I've tried to use modulo $3$ but it doesn't seem to be working. May I have some help?
 A: You cannot choose two items that have difference $1$, because $1$ divides any integer. Neither can you choose two items that have difference $2$, otherwise let them be $p$ and $p+2$, so we have $2\mid p+p+2=2(p+1)$.
Therefore, in any consecutive $3$ numbers you can pick at most one. Divide the set into $(1,2,3)$, $(4,5,6)$, $\dots$, $(2014,2015)$, such $672$ triples. Each triple can only contain one chosen number, so at most $672$ numbers are chosen.
A: Let $N$ denote the maximum number as in the problem. We claim that $N = 672$. We show this by proving that both $N \geq 672$ and $N \leq 672$ hold.
Proof of $N \geq 672$. Let
$$ S = \{1, 4, 7, \ldots, 2014\} = \{3k-2 : k = 1, 2, \ldots, 672 \}. $$
It is easy to show that $3 \mid a - b$ but $3 \nmid a + b$ for any distinct $a, b \in S$.
Proof of $N \leq 672$. Suppose otherwise that $N > 672$, and let $S$ be any maximal subset satisfying the desired property. We enumerate the elements of $S$ in increasing order, say $x_1 < x_2 < \ldots < x_{N}$. Then there exists $i$ such that
$$ x_{i+1} - x_i < 3, $$
for otherwise $x_{i+1} - x_i \geq 3$ for all $i$ and this implies
$$ 2014 \geq x_{|S|} - x_1 \geq \sum_{i=1}^{N-1} (x_{i+1} - x_i) \geq 3(N-1)
\geq 2016, $$
a contradiction. This shows that there exist $a, b \in S$ so that $a - b \in \{1, 2\}$. However,

*

*If $a - b = 1$, then clearly $a - b \mid a + b$.


*If $a - b = 2$, then $a + b = 2(b+1)$ is even and hence is divisible by $a - b$.
This contradicts our choice of $S$, and therefore $N \leq 672$.
