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.

Solution 1:

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!

Solution 2:

$$\text{We have}\quad \sum_{x=1}^n x^2 =\frac{n(n+1)(2n+1)}{6}\quad \text{and}\quad \sum_{x=1}^n x=\frac{n(n+1)}{2}$$

$$\text{If we divide the first by the second, we can readily see terms cancel so}\quad \frac{\sum_{x=1}^n x^2}{\sum_{x=1}^n x}=\frac{(2n+1)}{3}$$ Plugging in the value $99$ we get $R=2n+1\mod 3 \implies \frac{199}{3}=66\space R1 $

$$\text{For cubes we have}\quad \sum_{x=1}^n x^3=\frac{n^2(n+1)^2}{4}\implies R=n(n+1)\mod 2 \\ \implies \frac{9900}{2}=4950\space R0$$ Sums of odd powers are divisible by $\frac{n(n+1)}{2}$

Sums of even powers are divisible by $\frac{n(n+1)(2n+1)}{6} =\frac{n(n+1)}{2}\times\frac{2n+1}{3}\\$

I have in the past worked out summation formulas for powers up to $x^{31}$ the process is tedious and I would have trouble locating them right now. I could have gone farther but for lack of arbitrary precision. Any formula can be generated with a set of simultaneous equations represented in matrix form where the coefficients come from a modified Pascal's triangle or the formula's may be generated directly with selected Bernoulli numbers but that is beyond the scope of this question, Here is one more sample what we are looking for.

$$\sum_{x=1}^n x^4=\frac{n(n+1)}{2}\cdot \frac{(2n+1)(3n^2+3n-2)}{15}\implies R=(2n+1)(3n^2+3n-2))\mod 15$$ $$\implies \frac{5909902}{15}=393993\space R7$$

I disagree with the sequence suggested by one of the comments because it appears that, for $x^2, R=1$ and for $x^3, R=0$ and for $x^4, R=7$ (do check my math)

I can't see a general solution but you might play with the formulas for $x^1$ thru $x^{10}$ shown here.

$\textbf{Update: }$ I thought I had something but perhaps not or my math is bad in the last example below.

$R=n(n+1)(2n^2+2n-1) \mod 6 \implies \frac{196010100}{6} = 32668350\space R0$

$R = (2n+1)(3n^4+6n^3-3n+1) \mod 21\implies \frac{58506059899}{21} =2786002852\space R 7$

$R= n(n+1)(3n^4+6n^3-n^2-4n+2) \mod 12 \implies \frac{2910504979800}{12}. = 242542081650\space R0$

$R= (2n+1)(5n^6+15n^5+5n^4-15n^3-n^2+9n-1) \mod 45 \\ \qquad\qquad\qquad \implies \frac{965252482830701}{45} = 21450055174015\space R26$

$R= n(n+1)(n^2+n-1)(2n^4-4n^3-n^2-3n+3)\mod 10\\ \qquad\qquad\qquad \implies \frac{18446354100791100}{4950} = 3726536181978\space R0$

$R= (2n+1)(n^2+n-1)(3n^6+9n^5+2n^4-11n^3+3n^2+10n-5) \mod 11\\ \qquad\qquad\qquad \implies \frac{5732827616228279495}{11}= 173722048976614530 \space R5$

$\\$

The pattern so far is $1,0,7,0,7,0,26$ but, as indicated above, the last ones discovered may be math errors and the most likely "continuing" sequece is $0,7,0,7,0,7\cdots$