# Modular arithmetic

Hello,

What is the remainder when the following sum is divided by 4? $1^5 + 2^5 + 3^5 +...+ 99^5 + 100^5$

I feel like it has to do with modular arithmetic... I am trying to decompose every number but it seems to long and unnecessary. Any ideas?

P.S. thank you for your ideas. I got it. Please don't post solutions

• It's $0$, I believe. – Akiva Weinberger Sep 24 '14 at 17:04
• There's no need to compute all the numbers. Modular Arithmetic is the way, but you have also to get some regularity. Usually, the first thing to do is to try smaller numbers, to see if there are patterns – Exodd Sep 24 '14 at 17:07
• Hint: Any even number squared is divisible by 4 and any odd number power will give remainder 1. So count how many odds there are. – Ali Caglayan Sep 24 '14 at 17:08

HINT : Note that in mod $4$, $$1^5\equiv1,\ \ 2^5\equiv 0,\ \ 3^5\equiv (-1)^5=-1\equiv 3,\ \ 4^5\equiv 0$$ and that $$1+0+3+0\equiv 0,\ \ 100=4\times 25.$$

hint :take {1,2,3,4},{5,6,7,8} .....{97,98,99,100} as a set now each corresponding term in each set has same remainder when divided by 4 , so you effectively need to calculate only the remainder of $1^5+2^5+3^5+4^5$ w.r.t 4 and then multiply it by 25 and again find that numbers remainder w.r.t 4

$$1^5 \equiv 1 \pmod{4}$$ $$4\mid 2^5 \Rightarrow 2^5 \equiv 0 \pmod{4}$$ $$3^5 \equiv (-1)^5 \equiv -1 \pmod{4}$$ $$4^5 \equiv 0^5 \equiv 0 \pmod{4}$$

This means that every even number, when raised to the fifth power, is $0 \pmod{4}$. Thus the sum you asked about is equal to the number of $1 \pmod{4}$ numbers in $\{1,2,\dots 100\}$ minus the number of $3 \pmod{4}$ numbers in $\{1,2,\dots 100\}$.

Every fourth number from $1$ to $97$, inclusive, is $1 \pmod{4}$. There are $25$ of these.

Every fourth number from $3$ to $99$, inclusive, is $3 \pmod{4}$. There are $25$ of these as well, so

$$\displaystyle\sum\limits_{n=1}^{100} n^5 \equiv 0 \pmod{4}$$