Prove that $b_n = b_{n+100}$

Question

Let $b_n$ denote the units digit of $\displaystyle\sum_{a=1}^n a^a$. Prove that $b_n = b_{n+100}$.

I tried rewriting the sum, but didn't see how to prove the equality. For example, if $n = 178$ we have $$\displaystyle\sum_{a=1}^{178} a^a = (1^1+2^2+3^3+\cdots+78^{78})+(79^{79}+80^{80}+81^{81}+\cdots+178^{178})$$ and so we need to show that $79^{79}+80^{80}+81^{81}+\cdots+178^{178} \equiv 0 \pmod{10}$. Is there an easier way to prove the general result?

Answer 1

We can reduce the numbers to the residues modulo $10$, i.e:

$$79^{79} + 80^{80} + \cdots + 178^{178} \equiv 9^{79} + 0^{80} + \cdots + 8^{178} \pmod {10}$$

Now note that for each residues we have exactly $10$ numbers such that it appears in the base of the exponent. Group them and take one group. Now notice as their parity is equal the sum in the group is always even, so hence divisible by $2$. Now it's enough to prove it's divisible by $5$. Now if the base of the exponent is divisible by $5$ we're done, so assume it's not. Hence they are coprime. Now note that we can reduce the exponents modulo $4$, as $a^{4} \equiv 1 \pmod 5$ by Fermat's Theorem and as $\frac{4}{(4,10)} = 2$ the exponents will repeat in cycles of two, so we can group them in $5$ groups having same remainder, hence the sum is divisible by $5$.

---

For a better illustration of the last step check this:

$$79^{79} + 89^{89} + 99^{99} + 109^{109} + 119^{119} + 129^{129} + 139^{139} + 149^{149} + 159^{159} + 169^{169} $$ $$\equiv 9^{79} + 9^{89} + 9^{99} + 9^{109} + 9^{119} + 9^{129} + 9^{139} + 9^{149} + 9^{159} + 9^{169} $$ $$\equiv 9^{3} + 9^{1} + 9^{3} + 9^{1} + 9^{3} + 9^{1} + 9^{3} + 9^{1} + 9^{3} + 9^{1} \equiv 5(9^3 + 9^1) \equiv 0 \pmod 5$$

Answer 2

It is sufficient to prove that for each integer $k$

$$\sum_{a=t+1}^{t+100} a^a \equiv 0 \mod10$$

Consider a subsequence with indices $k,k+10,\dots,k+90$. We have $$ b(k) = k^k + (k+10)^{k+10} +\dots+(k+90)^{k+90} $$ Obviously, the following holds $$b(k) \equiv k^k + k^{k+10} + \dots+k^{k+90}\mod10$$ The right side could be rewritten $$k^k + k^{k+10} +\dots+k^{k+90} = k^k(1 + k^{10} +\dots+k^{90})$$

Lemma 1$$1 +k^{10} + k^{20}+\dots+k^{90} + k^{100} \equiv 1 \mod10$$ Proof. Here we use Fermat's little theorem, which states that $b$ coprime with $10$ sutisfies the condition $b^\varphi(10) = b^4\equiv 1\mod 10$. And for $b$ coprime with $5$ we have $b^\varphi(5) = b^4\equiv 1\mod 10$.
So, in the proof it is sufficient to check only the integers from $[0,9]$.

1. For the coprimes with $10$ we have $$1 +k^{10} + k^{20}+\dots+k^{100}\equiv 1 + 5(1+k^2)\equiv 1\mod10.$$
2. For $k = 5$ we have $5^{10i}(1-5^{100-10i})\equiv 1\mod10$, where the expression inside the brackets is even.
3. For an even $k$ we get $$1 + k^{10}(1 + k^{10}+\dots+k^{90})\equiv 1 \mod10,$$ where the expression in the brackets is divisible by $5$ because $$1 + k^{10}+\dots+k^{90}\equiv 5(1+k^2)\equiv 0\mod5,$$

Then $$k^k + k^{k+10} + k^{k+20}+\dots+k^{k+90} \equiv k^k(1-k^{100})\mod10$$

Lemma 2 $$a^a(1 - a^{100})\equiv 0\mod10,$$ for an integer $a$.

Proof.

1. For the comprimes with $10$, it is straightforward from Fermat's little theorem.

2. For $a \equiv 5\mod10$ we have even value for $(1-a^{100})$.

3. For an even number $a$ comprime with $5$, the quantity $(1-a^{100})$ is divisible by $5$ according to Fermat's little theorem.

4. For $a\equiv 0 \mod10$ it is obvious.

Finally, we can return to the initial sum and rewrite it

\begin{align} \sum_{a=k}^{k+100}a^a &\equiv k^k(1 - k^{100}) + (k+1)^{k+1}(1 - (k+1)^{100}) +\dots+(k+9)^{k+9}(1 - (k+9)^{100})\mod10 \end{align}

Where each term is divisible by $10$ according to Lemma 2. Therefore, the whole last sum is actually divisible by $10$.

Answer 3

We can use induction:

$b_{n+100} - b_n = b_n + \sum_{a = n+1}^{a = n+100}a^a - b_n$ = $\sum_{a = n+1}^{a = n+100}a^a = Y$

$b_{n+101} - b_{n+1} = b_n + Y + (n+1)^{n+1} - b_n - (n+1)^{n+1} = Y$

So if we assume $Y$ to be $0$ for $n$ it is $0$ for $n+1$.

Answer 4

$b_{n+100} = b_n + \left( \sum_{i=n+1}^{n+100} i^i \bmod 10\right)$

Since the Euler totient $\phi(10) = \phi(5)\cdot\phi(2) = 4 $, and $10$ is squarefree, we know that $a^k\equiv a^{k+4} \bmod 10$ for all positive $k$. This mean also $a^k\equiv a^{k+20} \bmod 10$.

Then $(a+20)^{a+20} \equiv a^{a+20} \equiv a^a \bmod 10$ and so $$\sum_{i=k+1}^{k+100} i^i \equiv 5\sum_{i=k+1}^{k+20}i^i \pmod{10}$$

Then the latter sum has $10 $ odd terms, and thus is even, so $$\sum_{i=k+1}^{k+100} i^i \equiv 5\sum_{i=k+1}^{k+20}i^i \equiv 10m \equiv 0 \pmod{10}$$

as required.