# What is the reminder when $1^1+2^2+3^3+\ldots+50^{50}$ is divided by 8

I have a sum that goes as follows $$P=1^1+2^2+3^3+\ldots +49^{49}+50^{50}.$$

The question is to find the reminder when $$P$$ is divided by 8.

Inorder to find this, I seperated $$P$$ into $$P_1$$ and $$P_2$$ where $$P_1=2^2+4^4+\ldots+50^{50},$$ $$P_2=1^1+3^3+\ldots+49^{49}.$$

And I realised that $$P_1 \text{ mod } 8 = 4$$ and $$P_2 \text{ mod } 8 = 1$$.

But I want to know if there is an easier, straightforward method for finding the answer.

• What is your not so straightforward method?
– Gary
Jun 27 '21 at 8:45
• Think about the evens and the odds separately. Modulo $8$, powers behave extremely regularly. Jun 27 '21 at 8:48
• Why not include how you got 5? Jun 27 '21 at 8:50
• @Gary I split them into even and odd terms and look at the sums separately. It kinda felt like a brute force method and I am looking for a more elegant solution, possibly from number theory. Jun 27 '21 at 8:56
• Edit and add that into question @MuhammedRoshan Jun 27 '21 at 8:57

This is still kind of brute force, but it's much more optimized, and it's a solution you can easily generalize to $$\sum_{k=1}^{n} k^k \pmod{m}$$ for higher values of $$n$$.

By the rules of modular arithmetic, when exponentiating, you can reduce the base modulo 8, and then break the terms into groups of 8. So, instead of writing $$1^1 + 2^2 + \cdots + 50^{50}$$, you can write $$(1^1 + 2^2 + \cdots + 8^8) + (1^9 + 2^{10} + \cdots + 8^{16}) + \cdots + (1^{41} + \cdots + 8^{48}) + 1^{49} + 2^{50}$$.

Further rearranging, we can write this as $$(1^1 + 1^9 + \cdots + 1^{49}) + \cdots + (8^8 + 8^{16} + \cdots + 8^{48}).$$

Now we can analyze this by casework, into 8 cases.

• $$1^{n}$$ = 1 for all n, so the first subcase sums to 7.
• $$2^2 = 4$$, and for any $$n\geq 3$$, $$2^n$$ is divisible by 8. Hence this second subcase is $$4 \pmod{8}$$.
• Note that $$3^8 = 1 \pmod{8}$$. Hence every term is the same mod 8. This contributes $$3 \cdot 6 = 18 = 2 \pmod{8}$$.
• Writing $$4^n$$ as $$2^{2n}$$, we see that all terms are divisible by 8.
• This is the same as the third case; $$5^8 = 1 \pmod{8}$$. Hence every term is the same mod 8, contributing $$5 \cdot 6 = 30 = 6 \pmod{8}$$.
• For all $$n\geq 3$$, $$6^n$$ is divisible by 8. Hence this case contributes nothing modulo 8.
• $$7^8 = 1 \pmod{8}$$. Applying the same logic, we have $$7\cdot 6=42 = 2 \pmod{8}$$.
• This last term contributes nothing because $$8 | 8^n$$ for all $$n\geq 1$$.

Adding up all the values, we get $$7+4+2+6+2=21 = 5 \pmod{8}$$. This is our answer.

• Yeah, or mod exponent of coprimes by $\phi(8)=4$ and get each section of $8$ terms contributes : $$1^1+3^{-1}+5^1+7^{-1}\equiv 0\pmod 8$$ except the $2^2$ term and the final 2 terms... Jun 27 '21 at 10:54