# 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?

-
Modulo 3, each summand is $1$. There are $n$ of them. – vadim123 Aug 31 '14 at 14:12
See $\#10$ of mathworld.wolfram.com/Congruence.html – lab bhattacharjee Aug 31 '14 at 14:15

$$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$.
Once you've convinced yourself of that (or otherwise) you may then use $a^k \equiv (a \bmod n)^k \pmod{n}$ without further proof :) – Thomas Aug 31 '14 at 15:09