Long Division Takes Forever!

We have $n^{2013} + 61=n^{2013}-1+62=(n^{667}-1)(n^{1334}+n^{667}+1)+62$ . Since the roots of $n^2+n+1$ are the complex cube roots of unity, $n^2+n+1$ divides $n^{1334}+n^{667}+1$ for integer values of $n$ . We are left to look for solutions which make $\dfrac{62}{n^2+n+1}$ an integer. By replacing the denominator with factors of 62, we get $-6,-1,0,5$ which sum to $-2$ .

Notice that

$n^{2013}+61$

$=(n^{3})^{671}+61$

$\equiv (n^{3}+n^{2}+n+1)^{671}+61$ $(mod$ ${n^{2}+n+1})$

$\equiv (n(n^{2}+n+1)+1)^{671}+61$ $(mod$ ${n^{2}+n+1})$

$\equiv 1^{671}+61$ $(mod$ ${n^{2}+n+1})$

$\equiv 62$ $(mod$ ${n^{2}+n+1})$

From the above, $n^{2}+n+1$ divides $n^{2013}+61$ iff $n^{2}+n+1$ divides $62$ .

Notice also that

$(-n-1)^{2}+(-n-1)+1$

$=n^{2}+2n+1-n-1+1$

$=n^{2}+n+1$

Thus, it is sufficient to replace $n$ with non-negative integers in order to look for all the possible integers $n$ . Substituting $n \geq 8$ will result in $n^{2}+n+1>62$ , which implies $n^{2}+n+1$ does not divide $62$ . Hence, there is no solution for $n$ in $[8, \infty)$ and also $(-\infty, -9]$ . Now by substituting $n$ with non-negative integers from $0$ to $7$ , we find that only $0$ and $5$ work. Therefore, $-1$ and $-6$ are solutions too. Summing up $-6$ , $-1$ , $0$ and $5$ gives $\boxed{-2}$ , which is the answer.