Elements in $GF(2)[x]$ and why $GF(4)=GF(2)[x]/(f)=\{0,1,x,x+1\}$ I'm trying to construct the elements of $GF(4)$ using an irreducible polynomial of degree two over $GF(2)$. Now I know the elements of $GF(4)=GF(2)[x]/(f)=\{0,1,x,x+1\}$... but I want to know how it is the set of these elements.
I know $f=x^2+x+1$ but what is $GF(2)[x]$? I know its the set of polynomials in an unknown $x$, with coefficients from
GF(2). So I thought $GF(2)[x]$ could be $=\{x^2, x^2+x+1, x, x^2+1, x^2+x, x+1\}$? but then I can't see how doing polynomial long division by $x^2+x+1$ gives me the set $\{0,1,x,x+1\}$
 A: For a ring $R$ the elements of $R[x]$ are the (formal) polynomials in the indeterminate $x$ with coefficients in $R$. We can write any of these uniquely as a finite sum
$$\sum a_k x^k .$$
In the case that $R$ is a field $\Bbb F$ (or more generally, whenever $R[x]$ is a Euclidean domain), we can perform polynomial long division. More precisely, for any polynomials $p, f\in \Bbb F[x]$, we can write
$$p(x) = a(x) f(x) + b(x)$$
for some unique polynomials $a$ and $b$, where $\deg b < \deg f$; $b$ is called the remainder.
In particular, if we take $$\Bbb F = GL(2) \qquad \textrm{and} \qquad f(x) = x^2 + x + 1 ,$$ then the remainder of any long division by $f$ has degree $< \deg f = 2$. But the only polynomials of degree $< 2$ in $GF(2)$ are $0, 1, x, x + 1$. Put another way, any element of $GF(2)[x]$ is congruent modulo $f(x)$ to one of those four polynomials, so $GF(4) = GF(2)[x] / (f)$ has four elements, namely the images of those four low-degree polynomials under the quotient map $$GF(2)[x] \to GF(2)[x] / (f) = GF(4).$$ In practice we often just (mildly abusively) just call those images by the same name, that is, write $$GF(4) = \{0, 1, x, x + 1\} .$$
A: $GF2[x]/(f)$ is the set of remainders of $GF2[x]$ when divided by $f$ (with addition and multiplication modulo $f$). Since $f$ is a degree two polynomial, the set of remainders is the set of polynomials of degree at most one.
A: If I am correct, your statement that $GF(2)[x]$ could be $\{x^2,x^2+x+1,x,x^2+1,x^2+x,x+1\}$ is not entirely correct. $GF(2)[x]$ does include those elements, but is much bigger. It is equal to: 
$GF(2)[x] = \{a_nx^n + a_{n-1}x^{n-1}+...+a_0x^0\text{ | } a_i \in GF(2) \}$.
With  $GF(2) = \{0, 1\}$.
For an actual answer on the question, the answer of Travis Willse does a great job explaining it!
