Question

Let $S = 2010 + 2011 + \cdots + 4018$. Compute the residue of $S$, modulo 2009.

Answer 1

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:

$S=\displaystyle\sum_{n=1}^{2008}n=\frac{2008\cdot2009}2$

where we invoke the formula

$\displaystyle\sum_{i=1}^ni=\frac{n(n+1)}2$

and so S ≡ 0 mod 2009.