# Construction of $p^n$ field

I heard that one can construct field based on $p^n$ elements where $p$ is prime. I tried with $p = n = 2$. It seemed easy as there are 2 groups which $\{0,1,2,3\}$ can form and 1 group formed by $\{1,2,3\}$. However each time I get into contradiction. Is there anything I missed or it is not possible to form $p^n$ element group?

-
en.wikipedia.org/wiki/… –  Qiaochu Yuan Aug 13 '10 at 17:01

There are finite fields of order $p^n$ for all prime powers $p^n$. They are often called Galois fields. But their additive groups are not cyclic (when $n\ne 1$). So for order $4$ one can have an addition table $$\begin{array}{cccc} 0&1&a&b\\ 1&0&b&a\\ a&b&0&1\\ b&a&1&0 \end{array}$$ but not an addition table $$\begin{array}{cccc} 0&1&2&3\\ 1&2&3&0\\ 2&3&0&1\\ 3&0&1&2 \end{array}.$$

-
This is the very first time that I hear a finite field referred to as a "Galois field", so it can't be that often. –  Álvaro Lozano-Robledo Aug 18 '11 at 12:45
@Álvaro: It is surely 'standard' to call them Galois fields. I even use the notation $GF(q)$ more often than $F_q$. Except here 'cause I try to be accomodating whenever I remember. –  Jyrki Lahtonen Aug 24 '11 at 20:32

First, any field of order $p^n$ will have characteristic $p$, so the underlying additive structure of the group is necessarily $(\mathbb{Z}_p)^n$; for order $2^2$, it follows that the additive structure has to be the Klein $4$-group (it cannot be cyclic of order $4$). Second, the multiplicative group of nonzero elements of any finite field is necessarily cyclic, so the multiplicative structure will always be isomorphic to $\mathbb{Z}_{p^n-1}$.

That said, trying to fit together the two structures abstractly is likely to prove very hard. Instead, the easiest way to construct such a field is as an extension of degree $n$ of the field $\mathbb{F}_p$ of $p$ elements. This is achieved by finding a monic irreducible polynomial of degree $n$ with coefficients in $\mathbb{F}_p$, call it $f(x)$, and considering the quotient $\mathbb{F}_p[x]/(f(x))$, where $\mathbb{F}_p[x]$ is the ring of polynomials with coefficients in $\mathbb{F}_p$, and $(f(x))$ is the ideal of all multiples of $f(x)$. Arithmetic of this field is easily computed using polynomial multiplication and long division (inverses can be found using the Euclidean algorithm).

It may not be immediately obvious that there is always a monic irreducible polynomial of degree $n$ over $\mathbb{F}_p$ for all primes $p$ and all positive integers $n$; but you can deduce that this is the case by showing that there in fact is a (unique up to isomorphism) field of order $p^n$ (consider the splitting field of $x^{p^n}-x$ over $\mathbb{F}_p$), and then showing that if $\alpha$ is a generator for the multiplicative group of this field, then the field is given by $\mathbb{F}_p(\alpha)$. General theory of field extensions then tells you the monic irreducible of $\alpha$ will do.

-

The very nice answer by Arturo Magidin describes explicit constructions of finite fields with $p^n$ elements. Let me work out a couple of explicit examples here.

For instance, you can construct a field $\mathbb{F}_4$ with $4$ elements by considering the quotient $\mathbb{F}_4=\mathbb{F}_2[x]/(x^2+x+1)$. Here $\mathbb{F}_2 = \mathbb{Z}/2\mathbb{Z}$ is a field with two elements, and notice that $x^2+x+1$ is irreducible over $\mathbb{F}_2$, because neither $0$ or $1$ are roots. Indeed, you can check that the $4$ polynomials $\{0, 1, x, 1+x\}$ form a complete set of representatives for the quotient of $\mathbb{F}_2$ modulo $(x^2+x+1)$, because any polynomial $q(x)$ of degree $2$ or higher is congruent to one of $0$, $1$, $x$ or $1+x$ modulo $x^2+x+1$ (just use long division of $q(x)$ by $x^2+x+1$). Here is the addition table for the field $\mathbb{F}_4$:

$$\begin{array}{c|cccc} + & 0 & 1 & x & 1+x \\ \hline 0 & 0 & 1 & x & 1+x \\ 1 & 1 & 0 & 1+x & x \\ x & x & 1+x & 0 & 1 \\ 1+x & 1+x & x & 1 & 0 \\ \end{array}$$ Notice that the shape of the multiplication table agrees with the one given by Robin Chapman. Here is the multiplication table for $\mathbb{F}_4$: $$\begin{array}{c|cccc} \times & 0 & 1 & x & 1+x \\ \hline 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & x & 1+x \\ x & 0 & x & 1+x & 1 \\ 1+x & 0 & 1+x & 1 & x \\ \end{array}$$ For example, $x(1+x)=x+x^2\equiv 1+(1+x+x^2)\equiv 1 \bmod (1+x+x^2)$.

Finally, let's construct a field with $9$ elements. This can be done by considering $\mathbb{F}_3/(x^2+1)$, since $x^2+1$ is irreducible over $\mathbb{F}_3$. Notice that $2\equiv -1\bmod 3$ is not a quadratic residue modulo $3$, thus $x^2+1\equiv x^2-2$ must be irreducible. Similarly, if $p$ is any prime with $p\equiv 3 \bmod 4$, then $x^2+1$ is irreducible and $\mathbb{F}_p/(x^2+1)$ is a field with $p^2$ elements.

-
Would you like vertical and horizontal lines in your table? I can add them, and then you'll see how it's done for future reference. –  Arturo Magidin Aug 18 '11 at 17:00
Yes, please! That would be nice. I am still a little confused about what TeX can be used with mathjax and what can't be used. –  Álvaro Lozano-Robledo Aug 18 '11 at 17:41
Done. I think those are enough, but if you want lines between every two columns, just add vertical lines in the declaration; to get lines between every two rows, just add an \hline between them. –  Arturo Magidin Aug 18 '11 at 17:45
That's great, thanks! It looks a lot better now. –  Álvaro Lozano-Robledo Aug 18 '11 at 17:52

Did you refer the Wikipedia article for constructing fields? Please refer the section of explicitly constructing finite fields.

Or if you want to be more advance you can refer this also: http://www.emis.de/journals/IJOPCM/Vol/09/IJOPCM(vol.2.3.1.S.9).pdf

-