What is the remainder when $1^n + 2^n + 3^n + \ldots + 99^n$ is divided by $1 + 2 + 3 + \ldots + 99$? My first idea on how to approach was to create a polynomial expansion for the first few terms and then try to find a pattern for the rest but this became cumbersome and I don't think that this is a right approach as this would quickly become a problem that involves factorials and I have not covered modular arithmetic, is there a way to approach this problem in such a way that does not involve using factorials with mods.
 A: An ad-hoc solution:
$n$ odd one can group $1^n+99^n, 2^n+98^n,...50^n$ to get $S_n$ divisible by $50$ and similarly $1^n+98^n,..49^n+50^n$ to get $S_n$ divisible by $99$ so as noted above the remainder is zero.
For $n$ even we notice that modulo $3$ each group $3k-2,3k-1, k=1,..33$ gives a sum that is $2$ modulo $3$ and since there are $33$ such sums, $S_n$ is then $3$ modulo $9$ as the multiples of $3$ give zero modulo $9$ for $n \ge 2$ but there is an odd number of them $15$ that are odd so $S_n=9\times (2m+1)+q$
Modulo $5$ we have to split into $n=4k+2$ when we have $20$ sums that are $0$ modulo $5$ so $S_n$ is divisible by $25$ and then $n=4k$ when similarly we get $S_n=80=5$ modulo $25$ and since $S_n$ is always even, $S_n$ is $30$ modulo $50$
Modulo $11$ we have two cases - $n$ multiple of $10$ we get then $S_n=90=2$ modulo $11$ ($9$ sums of $10$ each) and $n$ not multiple of $10$ when $S_n$ is divisble by $11$ (easily seen for $n \le 8$ since $S_n$ has a factor of $99$ and a denominator that doesn't contain $11$ and then by periodicity since $S_n=S_{n+10}$ modulo $11$)
Putting it together we get:
$n=2k+1$ we get $0$
$n=4k+2, n\ne 10m$ the remainders modulo $50,9,11$ are $0,3,0$ so we get $1650$
$n=4k, n \ne 10m$ the remainders modulo $50,9,11$ are $30,3,0$ so we get $3630$
$n=20k+10$ the remainders modulo $50,9,11$ are $0,3,2$ so we get $750$
$n=20k$ the remainders modulo $50,9,11$ are $30,3,2$ so we get $2730$ and that's all!
