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.

$$\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}$.
