abstract algebra - Constructing Finite Field Tables

Could someone please walk me through how to construct Finite Field tables? My biggest confusion is how to get the elements from the respectable fields.

For example. I'm asked to construct the table with 8, 9, and 16 elements.
My first thought is to take the elements and factor them as a product of primes: $2^3, 3^2, 2^4$ for each of the tables. However, I don't know how to come up with the polynomials.

Terras makes this statement in her book: "If $\alpha$ is a root of $f(x)$, the field obtained by adjoining $\alpha$ to $\mathbb{F}_p$ is $\mathbb{F}_q\cong \mathbb{F}_p[x]/f(x)$...Example: $\mathbb{F}_4\cong \mathbb{F}_2[x]/(x^2+x+1)=\mathbb{F}_2(\alpha)=\{0,1,\alpha,\alpha+1\}$"

How does she get that set of polynomials? Where does that polynomial that the cosets are formed from? For $\mathbb{F}_3$, what elements would I have in my set? I'm new to field theory, and this book makes a lot of jumps.

Answer

To combine and maybe condense the content of the comments, let’s say this:

If you want a (the) field with $p^m$ elements, you start with the field $\Bbb F_p=\Bbb Z/p\Bbb Z$. For simplicity, let’s call this field $k$. Then you find and fix a monic poynomial $f(x)$ of degree $m$ that’s irreducible over $k$.

Now your elements of $\Bbb F_{p^m}$, I’ll call this bigger field $K$, may be represented as polynomials of degree less than $m$, say $a_0+a_1x+\cdots a_{m-1}x^{m-1}$, with coefficients in $k$. You add two of these things in the obvious way, but for multiplication, you do the standard obvious thing, but then take your product $P(x)$, and work Euclidean Division of Polynomials on it, by dividing by $f(x)$ and using now the remainder (necessarily of degree $

Example: $p^m=9$, $k=\Bbb F_3$ with elements $\{0,1,2\}$. Since $-1=2$ is not a square there, you can use $x^2+1$ as your irreducible polynomial, and call your basic element now $i$ instead of $x$ — makes things very transparent. So now $(2+i)+(1+i)=2i$, but $(2+i)(1+i)=1$. Easy now to get the reciprocal of an element, too, same as in high-school. For higher degree than $2$, it’s a bit more of a pain to get reciprocal, but there are tricks that I won’t go into here.