Calculate $2^{2^{2006}} (mod3)$ Calculate $2^{2^{2006}} (mod3)$
Well, I believe it is not correct but can I say that:
$$2^{2^{2006}} (mod3) = 4^{2006} \equiv _3 1^{2006}(mod3) = 1$$
 A: You need to understand that $2^{2^{2006}} \neq 4^{2006}$. This is easily verified as $4^{2006} = (2^2)^{2006}\neq 2^{2^{2006}}$. So your solution doesn't work, unfortunately.
But here's how to do it intuitively, using a little pattern-recognition skill.
Notice that:

*

*$2^1 \equiv 2\ (\text{mod}\ 3)$

*$2^2 \equiv 1\ (\text{mod}\ 3)$

*$2^3 \equiv 2\ (\text{mod}\ 3)$

*$2^4 \equiv 1\ (\text{mod}\ 3)$
I hope you can see the general pattern here:
$$
2^{2n} \equiv 1\ (\text{mod}\ 3)
$$
and,
$$
2^{2n + 1} \equiv 2\ (\text{mod}\ 3)
$$
for $n \in \mathbb{N}$. That's just a fancy way of writing “$2$ raised to the power of something even will be $1$ mod $3$ and when raised to an odd power, it will be $2$ mod $3$”
Now, $2^{2006}$ is a very even number (make sure you understand why). Therefore, the answer to your question is:
$$
2^{2^{2006}}=2^{even}\equiv 1\ (\text{mod}\ 3)
$$
PS: You did manage to find the right answer, but your method was faulty. Hope my explanation cleared it up for you.
A: By Lil' Fermat, $2^2\equiv 1\mod 3$. Hence $2^n\equiv 2^{n\bmod2}\mod 3$. 
In particular $2^{2006}\equiv 0\mod 2$, so
$$2^{2^{2006}}\equiv 2^0=1\mod 3.$$
A: Hint $\ {\rm mod}\ n\!:\,\ \color{#c00}{n\!-\!1\equiv -1}\,\Rightarrow\, (\color{#c00}{n\!-\!1})^{\large 2k}\equiv (\color{#c00}{-1})^{\large 2k}\equiv 1\ $ by the Congruence Power Rule.
Remark $\ $ The proof you gave is inorrect because $\,\rm 2^{\large 2^{\Large N}}\!\!\neq (2^{\large 2})^{\large N},\,$ i.e. $\,2$^($2$^N)$\,\neq (2$^$2)$^N
A: $2^n\equiv 2\pmod 3$ when $n$ is odd and $2^n\equiv 1\pmod 3$ when $n$ is even. 
$2^{2006}$ is even.
A: Observe that $2^2 = 1$ mod $3$. Thus we are left with finding out what $r = 2^{2016}$ mod $2$ is and then we can write $2^{2^{2016}}$ as $2^{2k + r}$.
A: Prove by induction that $2^{2k}\equiv 1\pmod 3$ and $2^{2k+1}\equiv 2\pmod 3$ for $k\in\mathbb{N}$. So since $2^{2006}$ is even, then $2^{2^{2006}}\equiv 1\pmod 3$.
