congruence issue

Question

I need to understand why this :

$$(1+4+\ldots+4^{n−1})\equiv n \pmod3$$

Is that because

\begin{align} 1&\equiv -2 \pmod3\\ 4&\equiv 1 \pmod3\\ 4^{2}&\equiv1 \pmod3\\ \ldots&\equiv\ldots\\ 4^{n-1}&\equiv1 \pmod3 \end{align}

Am I right? Would you please explain to me more?

Answer 1

$$1 \equiv 1 \pmod 3$$ $$4 \equiv 1 \pmod 3$$ $$4^2 \equiv 1 \pmod 3$$ $$\dots$$ $$4^{n-1} \equiv 1 \pmod 3$$

$$1+4+ \dots +4^{n-1} \equiv 1+1+ \dots +1 \equiv n \pmod 3$$

Answer 2

Rewrite $4^n$ as $(3+1)^n$. Then, using the binomial expansion,http://en.wikipedia.org/wiki/Binomial_theorem we get $$3^n+(nC1)3^{n-1} +(nC2)3^{n-2}+...+(nCk)3^{n-k}...(nC(n-1))3 +1^n $$ , where $nCk$ means $\frac {n!}{k!(n-k)!}$ . Notice every term except the last one is divisible by 3 , so that the sum itself --meaning $3^n$ itself , is $1mod3$.