Powers of $x$ as members of Galois Field and their representation as remainders first question on math.stackexchange :)
I'm studying for a Cryptography - Communication Security exam, and it involves a certain quantity of number theory - finite field theory, so be warned: this is my first encounter with these topics, and you'll have to be extra-clear with me :)
I thought I was doing pretty well with the questions and exercises in $GF(4)$… then I hit $GF(8)$ and realized I'm still missing the point :(
I understand that to represent, let's say, $x^3$, the fourth element of $GF(8)$, I just take the result of the division of my irreducible polynomial of choice, let's say $x^3+x+1$, and I'm happy. I can then build addition and multiplication tables, and switch to and from a binary representation when it seems more convenient (e.g. when XORing with something else), and this also makes me happy.
But why do I start dividing $x^0$, $x^1$, $x^2$, etc.?
This sure seems like a sound idea when compared to “try some random polynomial“, but I can't figure why these are the candidates for being the members of the finite field? Why am I sure that this will generate all the elements?
Bonus question: $GF(4)$ seems to have a number of properties that are quite useful for manipulation. It seems obvious that $x+x \equiv 0$ in any $GF(2^n)$, but do $x^2 \equiv x+1$ or $x^3\equiv x^2+x\equiv 1$ always hold? Is this in any way dependent on the irreducible polynomial chosen? Are these predictable?
Please forgive me for any obvious error, and thanks in advance for any help.

It appears that you may mistakenly believe that every element of your finite field is a power of $\rm x$. Here is a very simple counterexample: put $\rm\; f(x) = (x^5-1)/(x-1) = x^4 + x^3 + x^2 + x + 1 \;$, which is irreducible $\pmod 2$. Then $\rm\; (x-1) \: f(x) = x^5 - 1 \Rightarrow \rm x^5 \equiv 1 \pmod{f(x)}$. This implies that the powers of $\rm x$ generate only 5 elements, not all 15 nonzero elements of $\rm GF(2^4)$ constructed with $\rm f(x)$. 
In fact there does exist an element whose powers generate all the nonzero elements of the finite field (said more technically: the multiplicative group is cyclic). Such generators are known as primitive elements. However, generally there is no simple closed-form known for such generators.
The reason that you didn't see this in $\rm GF(4)$ or $\rm GF(8)$ is because their multiplicative groups have prime order $3$ and $7,$ so every element $\ne 1,0 \:$ is a generator (by Lagrange's theorem the order of an element divides the order of the group which, being a prime $\rm p,$ forces the order to be $\rm p\:$ for elements $\rm \ne 1,0\:$).
