5
$\begingroup$

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.

$\endgroup$
6
  • 8
    $\begingroup$ What is your not so straightforward method? $\endgroup$
    – Gary
    Jun 27 '21 at 8:45
  • 1
    $\begingroup$ Think about the evens and the odds separately. Modulo $8$, powers behave extremely regularly. $\endgroup$
    – Milten
    Jun 27 '21 at 8:48
  • 1
    $\begingroup$ Why not include how you got 5? $\endgroup$
    – Oshawott
    Jun 27 '21 at 8:50
  • $\begingroup$ @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. $\endgroup$ Jun 27 '21 at 8:56
  • 1
    $\begingroup$ Edit and add that into question @MuhammedRoshan $\endgroup$
    – Martund
    Jun 27 '21 at 8:57
4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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... $\endgroup$ Jun 27 '21 at 10:54

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.