Finding $1^1+2^2+\cdots+99^{99}\pmod3$

Question

Calculate the following numbers in modular arithmetic. Justify your answers.
$$1^1+2^2+\cdots+99^{99}\pmod3.$$

I know that $$1^1 + 2^2 + \cdots + 99^{99} = \sum_{n=0}^{32} (3n + 1)^{3n + 1} + \sum_{n=0}^{32} (3n + 2)^{3n + 2} + \sum_{n=0}^{32} (3n + 3)^{3n + 3}.$$ Then I find that $$\sum_{n=0}^{32} (3n + 3)^{3n + 3}\equiv 0 \pmod3,$$ \begin{align*} &\mathrel{\phantom{=}}{} \sum_{n=0}^{32} (3n + 1)^{3n + 1} \equiv 3\sum_{n=0}^{32} n(3n + 1)^{3n}+\sum_{n=0}^{32}(3n + 1)^{3n}\\ &\equiv \sum_{n=0}^{32}(3(9n^3 + 9n^2 + 3n) + 1)^{n}\equiv \sum_{n=0}^{32}\sum_{r=0}^{n}\binom{n}{n-r}(3)^r(9n^3 + 9n^2 + 3n)^r1^{n-r}\\ &\equiv \sum_{n=0}^{32}1^n + 3\sum_{n=0}^{32}\left(\binom{n}{1}(9n^3 + 9n^2 + 3n)+\cdots+\binom{n}{n}(3)^{n-1}(9n^3 + 9n^2 + 3n)^n\right)\\ &\equiv \sum_{n=0}^{32}1^n \equiv 33 \equiv 0\pmod3, \end{align*}\begin{align*} &\mathrel{\phantom{=}}{} \sum_{n=0}^{32} (3n + 2)^{3n + 2} \equiv 3\sum_{n=0}^{32} (3n^2+4n)(3n + 2)^{3n}+\sum_{n=0}^{32}4(3n + 2)^{3n}\\ &\equiv \sum_{n=0}^{32}4(3(9n^3 + 18n^2 + 12n) + 8)^{n} \equiv 4\sum_{n=0}^{32}\sum_{r=0}^{n}\binom{n}{n-r}(3)^r(9n^3 + 18n^2 + 12n)^r8^{n-r}\\ &\equiv 4\sum_{n=0}^{32}\left(\binom{n}{n}8^n + \binom{n}{1}(3)(9n^3 + 9n^2 + 3n)+\cdots+\binom{n}{0}(3)(3)^{n-1}(9n^3 + 9n^2 + 3n)^n)\right)\\ &\equiv 4\sum_{n=0}^{32}\binom{n}{n}(9-1)^n\equiv 4\sum_{n=0}^{32}(9-1)^n\\ &\equiv 4\sum_{n=0}^{32}\left(\binom{n}{n}9^n+\binom{n}{n-1}9^{n-1}+\cdots+\binom{n}{n-1}1^n\right)\equiv 4\sum_{n=0}^{32}1^n\\ &\equiv 132\equiv 0\pmod 3. \end{align*} Therefore, $$1^1 + 2^2 + \cdots + 99^{99}\equiv 0 + 0 + 0 \equiv 0\pmod3.$$

Am I correct? Is it correct that $\sum\limits_{n=0}^{32}(3n + 1)^{3n + 1} \equiv 0\pmod3$ and $\sum\limits_{n=0}^{32} (3n + 2)^{3n + 2}\equiv 0\pmod3$?

Answer 1

We sum terms of the shape $n^n$ for $n$ running between $1$ and $99$. We consider the cases:

• $n=0$ modulo $3$, then $n^n\equiv 0^n$ is also zero mod $3$.
• $n=1$ modulo $3$, then $n^n\equiv 1^n$ is also one mod $3$.
• $n=-1$ modulo $3$, then $n^n$ is $(-1)^n$ mod $3$.

The corresponding subsums are

• $0+0+\dots+0=0$ modulo $3$,
• $1+1+\dots+1$ (where we add $33$ terms, namely $3\cdot 0+1$, $3\cdot 1+1$, ... $3\cdot 32+1$) modulo $3$, with a total of zero modulo $3$,
• $1-1+1-1+\dots+1=1$ modulo $3$, an alternating sum of reminders modulo $3$, the last one being an even power (for $n=98$). The total contribution here is $1$ modulo $3$.

So we add and get $1$ modulo $3$ in the final.

---

Computer check, sage:

sage: sum( [ GF(3)(n)^n for n in [1..99] ] )
1

Answer 2

Exploiting periodicity reduces the sum calculation to the sum of the final $3$ terms, as follows.

The terms have period $\,6\,$ by $\!\bmod 3\!:\ (n\!+\!6)^{\large n+6}\!\equiv n^{\large n}\, $ (true for $\,n\equiv 0, \pm 1$ so for all $\,n>0)$

so each period sums to $ 1^2\!+\!2^2\!+\cdots+6^6\equiv \color{#0a0}{1\!+\!1\!+\!0}\!+\!1\!+\!2\!+\!0\equiv \color{#c00}2$

Before $\ 91 = 1 + 6\cdot 15\,$ are $\,15\,$ periods, $ $ having total sum $\,\equiv 15\cdot\color{#c00}2\equiv 0\,$ by $\,15\equiv 0$

Hence the sum is $\,\equiv\, \underbrace{91^{91}+ \cdots+96^{96}}_{\Large {\rm period\ \Sigma}\ \equiv\,\ \color{#c00}2\ \ } +\, \underbrace{97^{97}\!+98^{98}\!+99^{99}}_{\Large\ \color{#0a0}{1\ +\ 1\ +\ 0}\quad\ }\equiv\, \color{#c00}2\!+\!\color{#0a0}{1\!+\!1\!+\!0}\equiv 1$

Remark $ $ The same idea applies for any sum of periodic terms over an interval of $k$ periods plus a partial period. The sum is $k$ times the period sum plus the sum of the terms in the partial period.

Answer 3

Hint: If $x \equiv 0 \mod 3$ (and $x \ge 1$), $x^x \equiv 0 \mod 3$. If $x \equiv 1 \mod 3$, $x^x \equiv 1 \mod 3$. If $x \equiv 2 \mod 3$ and is even, $x^x \equiv 1 \mod 3$. If $x \equiv 2 \mod 3$ and is odd, $x^x \equiv -1 \mod 3$.