# How to find the remainder of big number divisions using congruences?

I´m asked to find the remainder of dividing $$\sum_{i=0}^{1080}i^5$$ by $$14$$. How can I do this using only basic results from modular arithmetic? Only one thing comes to my mind, here's my idea: we know that each number has a representative $$r$$ in the class of $$\pmod{14}$$, that satisfies $$0\leq r<14$$, so in order to simplify things, it is only needed to find this representative for $$n^5$$ for the integers $$n$$ between $$0$$ and $$13$$, because, for example, if I wanted to find the residue of $$\sum_{i=0}^{27}i^5$$ divided by $$14$$, then assuming I know that $$k_n$$ is the representative of $$n$$ for each $$n\in\{ 0,\dots,13 \}$$, then $$14\equiv0\pmod{14}$$ implies $$14^5\equiv0^5\equiv k_0\pmod{14}$$, $$15\equiv1\pmod{14}$$ implies $$15^5\equiv1^5\equiv k_1\pmod{14}$$, and so on until $$27^5\equiv13^5\equiv k_{13}\pmod{14}$$. In this way, it is now possible to know that, given that $$\begin{equation*}\sum_{i=0}^{27}i^5=\sum_{i=0}^{13}i^5+(i+14)^5 \end{equation*}$$, then for $$i\in\{ 0,\dots,13 \}$$, $$i^5\equiv (i+14)^5\pmod{14}\Rightarrow i^5+(i+14)^5\equiv2i^5\equiv2k_i\pmod{14}$$, which implies that: $$\begin{equation*}\sum_{i=0}^{13}i^5+(i+14)^5\equiv\sum_{i=0}^{13}2k_i\equiv R_k\pmod{14} \end{equation*}$$ where $$R_k$$ is the representative of $$\sum_{i=0}^{13}2k_i$$ in $$\mathbb{Z}_{14}$$. That's the residue we're looking for.

Following the pattern, I'd need to find out how many times a number which is congruent to a number between $$0$$ and $$13$$ in $$\mathbb{Z}_{14}$$ appears between $$0$$ and $$1080$$, and then rewrite the original sum in terms of how many times the "repeated" (by this I mean in the sense that they are equivalent in $$\mathbb{Z}_{14}$$) numbers appear.

(I already did this, but as I said, it's a very long and tedious process).

Another idea is to use the formula for the sum of the first $$n$$ fifth powers.

Any other idea of an easier process, or a check to mine would be really appreciated. Thanks in advance.

• By the Chinese Remainder Theorem you only need to consider the congruence mod $7$ and mod $2$. – Lukas Kofler Apr 18 '20 at 23:54

## 2 Answers

The mapping $$x\mapsto x^5$$ is a bijection on integers modulo $$14$$ (its inverse is itself),

and $$1080=1078+2=77\times14+2$$.

Therefore, $$\sum\limits_{i=0}^{1080}i^5\equiv\sum\limits_{i=0}^{1077}i+1078^5+1079^5+1080^5$$

$$\equiv77\sum\limits_{i=0}^{13}i+0^5+1^5+2^5\equiv77\times\dfrac{13\times14}2+1+32$$

$$\equiv7\times odd+1+32\equiv7+33=40\equiv12\bmod14.$$

• How can you prove it's bijective? I've been trying and I just can't seem to get anywhere. – Bryan Castro Apr 19 '20 at 17:54
• One way would be to compute $0^5, (\pm1)^5, (\pm2)^5, (\pm3)^5, (\pm4)^5, (\pm5)^5, (\pm6)^5,$ and $7^5$ mod $14$; another way, which I alluded to, is to show that $n^7\equiv n\bmod 2$ and $7$ so $\bmod 14$, and therefore $(n^5)^5=n^{25}=(n^7)^3n^4\equiv n^3n^4\equiv n^7\equiv n\bmod14$, so $n\mapsto n^4$ is bijective because it has an inverse – J. W. Tanner Apr 19 '20 at 19:00
• I made a typo in my comment above; I meant $n\mapsto n^5$ where I typed $n\mapsto n^4$ – J. W. Tanner Apr 19 '20 at 20:21
• Hmm, that seems very good. Thank you very much! I would upvote your answer but I'm not able until I get 15 reputation. Greetings. – Bryan Castro Apr 20 '20 at 1:17

We have

$$\tag 1 \displaystyle \sum_{i=0}^{13}i^5 \equiv 0 + + 7^5 +\sum_{i=1}^{6}\bigr(i^5+(-i)^5\bigr) \equiv 7^5 \equiv 7 \pmod{14}$$

Also, since

$$\quad 1081=77\times14+3$$ we can write

$$\tag 2 \displaystyle \sum_{i=0}^{1080}i^5 \equiv 77\cdot7 + 0^5 + 1^5 + 2^5 \equiv 7 + 0 + 1 + 4 \equiv 12\pmod{14}$$