Find remainder when $1^{5} + 2^{5} \cdots +100^{5}$ divided by 4

I'm studding D.M Burton & want to solve: Find remainder when $1^{5} + 2^{5} \cdots +100^{5}$ divided by $4$. . Please help me by giving your solution to it. I'm new comer to number theory so please don't use theorems above Theory of Congruence.

• What have you tried? Hint: calculate the values of $n^4$ mod $4$ for a few small values of $n$. – Ethan Bolker Apr 10 '16 at 14:33
• @Ethan Bolker i got at last $\frac{100}{4} = 0$ (in terms of remainder) – mnulb Apr 10 '16 at 14:35

Apply "$\bmod4$" on each term, then you get:

$\sum\limits_{n=1}^{100}n^5\equiv25\sum\limits_{n=1}^{4}(n\bmod4)^5\equiv25(1^5+2^5+3^5+4^5)\equiv32500\equiv0\pmod4$

• Is there any theory relating to closed form also? – mnulb Apr 10 '16 at 14:43
• @Ayushakj: Sorry, I don't understand the question. – barak manos Apr 10 '16 at 14:47
• Means u apply congruence in closed form (sigma & sequence,series). I want to say is there any rule that u used in starting two steps. you converted upper limit 100 to 4 by introducing $(n\ mod\ 4)^5$ & removed $n^5$.If so please help me. – mnulb Apr 10 '16 at 14:54
• @Ayushakj: You can apply "mod" on each term separately. I took the "$25$" out of the sum, because there are $4$ different cases, and each one of them appears exactly $25$ times. – barak manos Apr 10 '16 at 15:45

It is congruent to $1+0+3+0+1+0+3+0+...+1+0+3+0$ which is congruent to $0$ (mod 4).

So the remainder is $0$.

$$0^5=0 \pmod4$$ $$1^5=1\pmod4$$ $$2^5= 0 \pmod4$$ $$3^5=3\pmod4$$ $$1^5+2^5+...+100^5=25(1^5+2^5+3^5+4^5)\pmod4=25*0\pmod4=0\pmod4$$

You can do it even without knowledge of congruences, we have that $1^5 + 2^5 + ... + n^5= \dfrac {(n(n+1))^2(2n^2+2n-1)}{12}$, now set $n=100$ to get $1^5 + 2^5 + ... + 100^5 = \dfrac {(100 \cdot 101)^2 (2 \cdot 100^2 + 2 \cdot 100 - 1)}{12}=4 \cdot \dfrac {4 \cdot 25^2 \cdot 101^2 \cdot 3 \cdot 6733}{12}$ so your number is divisible by $4$.

• $((n)(n+1))^2$ is multiple of 4. – Takahiro Waki Apr 10 '16 at 15:05
• @TakahiroWaki Yes it is, beacuse that is the square of even number. – Farewell Apr 10 '16 at 15:07

Another way is to use the "paired element" approach... Since $a^5+b^5=(a+b)(a^4-a^3b+a^2b^2-ab^3+b^4)$, we have

$$1^5+99^5+2^5+98^5+\dots+ 50^5+100^5\\ =100(1-99+99^2-99^3+99^4)+100(2^4-\dots)+\dots+100(49^4-\dots)+2^5\cdot(25)^5+100^5\\ \equiv 0\pmod 4$$

• Also $≡0(mod 25)$ – Takahiro Waki Apr 10 '16 at 15:03
• @TakahiroWaki: very true – abiessu Apr 10 '16 at 15:04