Cfrgtkky

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.

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

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 33cdot (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^3equiv npmod3$ as $n^3-n=n(n-1)(n+1)$ is the product of three consecutive integers

We have $sum_{r=1}^mr^3equivsum_{r=1}^mrpmod3$

$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}^nkright)^2
$$
So,
$$
sum_{k=1}^{99}k^3equivleft(sum_{k=1}^{99}kright)^2equivfrac{(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.