# congruence issue

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?

#### Solutions Collecting From Web of "congruence issue"

$$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$$

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