<s>[INST] How do I find the remainder of $4^0+4^1+4^2+4^3+ \cdots + 4^{40}$ divided by 17? 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.
 [/INST] 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$.
</s>