# 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.

• One way would be to identify the patterns as $n$ increases for each prime factor/prime power of $1+2+3+\dots+99 = 4950 = 2\cdot 3^2\cdot 5^2\cdot 11$, then combine those patterns into the overall result... – abiessu Nov 10 at 18:37
• The answer is $0$ for $n=3$ by Nichomachus' theorem; in general, $\sum_1^n k^n$ is a polynomial function with rational coefficients of $\sum_1^n k$ for all odd $n$ (this is a result of Faulhaber). – Prasun Biswas Nov 10 at 18:42
• For all odd $n$, the remainder is zero. See artofproblemsolving.com/community/c4h40038, comment #55 for an elementary proof. – player3236 Nov 10 at 18:49
• Empirically, the sequence of remainders is periodic: $0,1650,0,3630,0,1650,0,3630,0,750,0,3630,0,1650,0,3630,0,1650,0,2730,\dots$ – lhf Nov 10 at 19:02
• @FATEH ALIYEV You might ask yourself. Do you want the remainder before or after the sum of powers over the sum of integers is reduced by their GCD. Note my 2nd answer because my first answer did the division after reduction, – poetasis Nov 11 at 8:34

$$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!

$$\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$$

• The answer Conrad gave is better than mine because there is a difference in remainder once a number and its "mod" have both been divided by their GCD. The proper answers, I think, should be those in my post multiplied by that GCD. – poetasis Nov 18 at 2:26