How do I find the remainder of $4^0+4^1+4^2+4^3+ \cdots + 4^{40}$ divided by 17?

Question

Recently I came across a question,

Find the remainder of $4^0+4^1+4^2+4^3+ \cdots + 4^{40}$ divided by 17?

At first I applied sum of G.P. formula but ended up with the expression $1\cdot \dfrac{4^{41}-1}{4-1}$. I couldn't figure out how to proceed further. Secondly I thought of using the fact $(a+b+\cdots) \pmod {17} = (r_a+r_b\dots) \pmod {17}$ but it is getting more messier.

Please explain in detail. And also mention the formula being used.

Answer 1

HINT:

Observe that for any non-negative integer $a,$ $$1+4+4^2+4^3=(1+4)(1+4^2)\equiv0\pmod{17}$$

$$\implies\sum_{a=m}^n4^{4a}(1+4+4^2+4^3)\equiv0\pmod{17}$$

Here $m=0,n=9$

Answer 2

Hint: $$4^2 = 16 \equiv -1 \mod 17$$ $$4^4 \equiv (-1)^2 \equiv 1 \mod 17$$

Answer 3

$$\frac{4^{41}-1}{4-1}\equiv \frac{2^{82}-1}{4-1}\equiv \frac{2^2-1}{4-1}\equiv 1\pmod{17}.$$ Fermat's little theorem was used: $2^{16}\equiv 1\pmod{17}$ implies: $$ 2^{82} = 2^{5\cdot 16+2} = 4\cdot \left(2^{16}\right)^5 \equiv 4\pmod{17}.$$

---

Another approach. Let $a_n = 4^0+4^1+\ldots+4^n$. Then obviously $a_{n+1}=4a_n+1$, so given $a_n\pmod{17}$, to compute $a_{n+1}\pmod{17}$ is straightforward. $a_0=1$, so our sequence $\pmod{17}$ goes this way: $$ 1 \to 5 \to 4 \to 0 \to 1 \to 5 \to 4 \to \ldots $$ hence it is $4$-periodic. That implies $a_{40}\equiv a_{0}\equiv 1\pmod{17}$.

Answer 4

If you calculate $4^{k}\ (\operatorname{mod}\ 17)$ for some $k$'s, you might quickly notice that the values are periodically $1,4,-1,-4$. This is not coincidence, since $4^4 \equiv 1 \ (\operatorname{mod}\ 17)$, and thus $$4^{4k+l}\equiv 4^{4k}\cdot 4^l \equiv (4^4)^k\cdot 4^l \equiv 4^l \ (\operatorname{mod}\ 17)$$ So, we conclude $$4^{4k+1}+4^{4k+2}+4^{4k+3}+4^{4k+4}\equiv 4 + (-1) + (-4) + 1 \equiv 0 \ (\operatorname{mod}\ 17)$$ and can calculate $$4^0+4^1+4^3+\cdots 4^{40} \equiv (4^0+4^1+4^3+4^4)+\sum_{k=1}^9(4^{4k+1}+4^{4k+2}+4^{4k+3}+4^{4k+4}) \equiv 4^0+4^1+4^3+4^4 \equiv 1 + 4 + (-4) + 1 \equiv 2\ (\operatorname{mod}\ 17)$$ Of course, if $4^2$ is accidentally missing in the question, sum just as easily evaluates to $1$.