-1
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ Use $n^3\equiv n\pmod3$. $\endgroup$ – Angina Seng Dec 27 '18 at 5:42
  • $\begingroup$ math.stackexchange.com/questions/1328798 $\endgroup$ – Andrei Dec 27 '18 at 5:43
  • 1
    $\begingroup$ 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. $\endgroup$ – John Omielan Dec 27 '18 at 5:46
  • $\begingroup$ @LordSharktheUnknown ah thanks. I guess the $(x+1)^3$ method would've revealed that. $\endgroup$ – samerivertwice Dec 27 '18 at 5:46
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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$$
| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.