What's $1^3+2^3+3^3+\cdots+99^3$ modulo $3$?

What's the remainder when the sum

$$1^3+2^3+3^3+\cdots+99^3$$ is divided by $$3$$?

Background:

I saw this question on MSE but it was closed and I wanted to learn how to approach it. The help given to the asker had failed to bring the question up to an acceptable standard.

I can solve it but I doubt my methods are efficient.

One way is to start by removing every third term. Then the first two terms of the remaining sequence can be removed, and so on... a pattern may emerge.

Another way is to look at the expansion of $$(x+1)^3$$ and see what it does to the residues for each $$x$$, then sum over that by induction.

But I'm sure my inventions aren't very efficient.

• Use $n^3\equiv n\pmod3$. – Angina Seng Dec 27 '18 at 5:42
• math.stackexchange.com/questions/1328798 – Andrei Dec 27 '18 at 5:43
• In general, note that you can handle the terms in groups of $3$ as $n + 3 \equiv n \pmod 3$, and also use that $n^3 \equiv n \pmod 3$ as Lord Shark the Unknown stated above. – John Omielan Dec 27 '18 at 5:46
• @LordSharktheUnknown ah thanks. I guess the $(x+1)^3$ method would've revealed that. – samerivertwice Dec 27 '18 at 5:46

By Fermat's little theorem $$a^3\equiv a\pmod3$$. Then you have $$\sum_{k=1}^{99} k=\frac{(99)(100)}2=50\cdot 99\equiv 0\pmod3$$.

\begin{align} \sum_{i=1}^{99}i^3 &= \sum_{i=0}^{32} (3i+1)^3 + \sum_{i=0}^{32} (3i+2)^3 + \sum_{i=0}^{32} (3i+3)^3 \\ &\equiv \sum_{i=0}^{32} 1^3 + \sum_{i=0}^{32} 2^3 + \sum_{i=0}^{32} 0^3 \pmod{3}\\ &\equiv \sum_{i=0}^{32} 1^3 + \sum_{i=0}^{32} (-1)^3 + \sum_{i=0}^{32} 0^3 \pmod{3}\\ &\equiv 0 \pmod{3} \end{align}

Split the numbers from $$1,\ldots, 99$$ in

• $$33$$ with remainder $$1$$
• $$33$$ with remainder $$2$$
• $$33$$ with remainder $$0$$ $$1^3 + 2^3 + \cdots + 99^3 \equiv 33\cdot (1^3+2^3+0^3) \equiv 0 \mod 3$$

consider these observations:

$$1 = 1 \pmod 3$$ $$2 = -1 \pmod 3$$ $$3 = 0 \pmod 3$$

This becomes:

$$33(1^3+(-1)^3+0) \equiv 33(1+(-1)+0) \equiv 33(0) \equiv 0 \pmod 3$$

Hint:

$$n^3\equiv n\pmod3$$ as $$n^3-n=n(n-1)(n+1)$$ is the product of three consecutive integers

We have $$\sum_{r=1}^mr^3\equiv\sum_{r=1}^mr\pmod3$$

$$\equiv \dfrac{m(m+1)}2$$

Alternatively $$\sum_{r=1}^m r^3=\dfrac{m^2(m+1)^2}4$$

From $$a^{3} + b^{3} = (a+b)(a^{2}-ab+b^{2})$$, you have $$a+b|a^{3} +b^{3}$$ and \begin{align} &1^{3} + 2^{3} + 3^{3} + \cdots + 97^{3} + 98^{3} + 99^{3} \\ &= (1^{3} + 2^{3}) + (4^{3} + 5^{3}) + \cdots + (97^{3}+98^{3}) + (3^{3}+6^{3} + \cdots + 99^{3}) \end{align} is a multiple of 3.

Another method is to use the identity

$$\sum_{k=1}^nk^3=\left(\sum_{k=1}^nk\right)^2$$ So, $$\sum_{k=1}^{99}k^3\equiv\left(\sum_{k=1}^{99}k\right)^2\equiv\frac{(99)^2(100)^2}{4}\equiv0\ (\mod3)$$

Yet another method is to use that $$(x-1)^3=x^3-3x^2+3x-1$$ and $$(x+1)^3=x^3+3x^2+3x+1$$, so $$(x-1)^3+x^3+(x+1)^3 = 3x^3+6x$$, which is divisible by three. This shows that any three consecutive numbers, when cubed, add up to zero modulus three.

You can also calculate that sum using

$$\sum_{i=0}^{i=n}i^3=\dfrac{n^2(n+1)^2}{4}$$

Here: $$\sum_{i=0}^{i=99}i^3=\dfrac{99^2(99+1)^2}{4}$$ which is clearly divisible by 3.