Simplifying $2^{30} \mod 3$ I simply cannot seem to get my head around this subject of mathematics. It seems so counter-intuitive to me. 
I have a question in my book: Simplify $2^{30}\mod 3$
This is my attempt: $2^{30}\mod 3 = (2\mod 3)^{30}$ (using the laws of congruences). 
$2\mod 3$ must be equal to $2$, right? $0\cdot 3 + 2 = 2$ then the rest is "2". Therefore, I concluded that $2^{30}$ is the answer. However, my book says $1$. How can this be? Can anyone explain this to me? It's probably really easy, and I feel kind of stupid for asking, but I simply don't get it.
And also, are there any sites on the internet that provide similar problems with which you can learn the concepts?
Thank you. 
 A: Because $2 \equiv -1 \pmod 3$, we have
$$ 2^{30} \equiv (-1)^{30}\equiv 1 \pmod 3.$$
A: Note that $\gcd(2, 3) = 1$, and so $2^{3-1} \equiv 1 \pmod 3$ by Fermat's Little Theorem. We have
$$2^{30} \equiv (2^2)^{15} \equiv 1^{15} \equiv \boxed{1} \pmod 3.$$
A: You are being asked to find the least non-negative residue modulo $3$ (or perhaps the residue with least absolute value. For the first the options are $0,1,2$ and for the second you can choose $-1,0,1$. The residue is essentially the same as the remainder on division by $3$.
Now $2^{30}=(2^{10})^3=(1024)^3$ is of the order of $10^9$ and the point is to find a strategy to get a smaller value.
Now $1024\equiv 1$ is easy to establish. But the easiest route, once you have correctly identified the problem, is to notice that $2\equiv -1$. Quite often, these power problems involve finding a small power which is equivalent to $\pm 1$, since these are easy to work with.
For these kinds of problems - especially if they become more advanced - you should have Fermat's Little Theorem and the Euler-Fermat theorem to hand. But first get very used to the residue being the remainder on division.
