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.