Construct a field from irreducible polynomial

I'm having some difficulties understanding how I'm supposed to construct a field of order $p^r$(where p is a prime number and $r\geq1$) using an irreducible polynomial of degree $r$ in $Z_p[x]$.

(All the $Z$ symbols denote the symbol for the ring of integers.).

The theory states the following

"Let $k(x)$ be an irreducible polynomial of degree $r$ in $Z_p[x]$ and let ~ be the equivalence relation on $Z_p[x]$ defined by

$a(x)$ ~ $b(x) \Leftrightarrow a(x) - b(x)$ is divisible by $k(x)$.

Then the set of equivalence classes of ~ in $Z_p[x]$ is a field of order $p^r$

An example using this is the following:

Construct a field of order 4 by using the irreducible polynomial $x^2 + x + 1$ in $Z_2$.

The solution states that the field consists of the following 4 elements:

{0, 1, x, x+1}

But exactly how have they deduced that from the theory? I understand why the order is 4. But I'm not understanding how they deduced that the elements of the field should be those mentioned above.

• When any polynomial in $\mathbb Z_2[x]$ is divided by $x^2+x+1$, the remainder is necessarily one of $0, 1, x, 1+x$ and so these four polynomials can be taken to be the representatives of the four equivalence classes of $\sim$ in $\mathbb Z_2[x]$. – Dilip Sarwate Dec 15 '16 at 17:03
• Oh now I get it! Thanks for clearing it up! I was wondering how they were respective equivalence classes, but I get it now! – user3043462 Dec 15 '16 at 17:50

The idea here is the following general theorem:

Let $R$ be a commutative ring, and suppose $I\subset R$ is a maximal ideal of $R$, then the quotient ring $R/I$ is a field.

An ideal $I\subset R$ is a set such that $ra\in I$ and $ar\in I$ for each $a\in I$ and $r\in R$, and a maximal ideal is a proper ideal not properly contained in any other proper ideal. Furthermore, the ring $R/I$ is simply the set of all equivalence classes under the relation $r_1\sim r_2$ if and only if $r_1-r_2\in I$.

I'll leave it as an exercise for you to show:

1. The set of polynomials $\mathbb Z_p[x]$ is a commutative ring
2. The set $(k(x)):=\{a(x)k(x):a(x)\in \mathbb Z_p[x]\}$ is an ideal (the ideal generated by the polynomial $k(x)$)
3. If $k(x)$ is irreducible, then $(k(x))$ is a maximal ideal
4. $\mathbb Z_p[x]/(k(x))$ is a field of order $p^d$, for $d=\deg(k(x))$ (Note that $\mathbb Z_p[x]/(k(x))$ is the same as $\mathbb Z_p[x]/\sim$ for the relation you stated).

In your example for $\mathbb Z_2[x]/(x^2+x+1)$, notice that $x^2\sim -(x+1)$, so all equivalence classes in your field have a linear representative element, and since $\{0,1,x,x+1\}$ are the only linear elements of $\mathbb Z_2[x]$, you know these are the only ones.

The equivalence relation you gave is precisely the equivalence relation which defines the coset space of $Z_p[x]/(f(x))$, which is a field because $f(x)$ is irreducible, and hence $(f(x))$ is a maximal ideal. You can use one of the isomorphism theorems (the "lattice one?") to show that a quotient of a ring by a maximal ideal has no nonzero proper ideals, and thus is a field.

• What I don't understand is how I get that {0, 1, x, x+1} are the elements of the field, using the irreducible polynomial x^2+x+1 in Z_2 ? How do I use the irreducible polynomial to get those elements? – user3043462 Dec 15 '16 at 16:50
• @user3043462 Perhaps it would be instructive for you to work out some simple examples. First consider the case $f(x) = x$, or $f(x) = x+1$. Next consider the case $f(x) = x^2+a$ (here you need to figure out which values of $a$ will result in $f(x)$ being irreducible). – oxeimon Dec 15 '16 at 16:54