Notice that
2010 ≡ 1 mod 2009
2011 ≡ 2 mod 2009
2012 ≡ 3 mod 2009
...
4017 ≡ 2008 mod 2009
4018 ≡ 0 mod 2009
So really, S is just the sum of the first 2008 positive integers:
[tex]S=\displaystyle\sum_{n=1}^{2008}n=\frac{2008\cdot2009}2[/tex]
where we invoke the formula
[tex]\displaystyle\sum_{i=1}^ni=\frac{n(n+1)}2[/tex]
and so S ≡ 0 mod 2009.
