Determine the greatest natural number $n$ such that for every set $S$ of 2015 different integers, there exist two subsets of $S$ (each subset can have at least one element and the subsets do not need to be disjoint) such that the sum of the elements in each subset is divisible by $n$.

Let's think step by step and output the final answer within \boxed{}.
user