# Thread: Nature and character of Finite Fields of small order

1. i am studying finite fields and trying to get an idea of the nature of finite fields.

In order to achieve this understanding I am bring to determine the elements and the addition and multiplication tables of some finite fields of small order.

For a start I am trying to determine the elements andthe addition and multiplication tables of the finite field of order 8.

Can someone show me how to get started on this problem?

Peter

***EDIT*** Just reflecting that maybe I should have started with $\displaystyle \mathbb{F}_2 \text{ and } \mathbb{F}_3$ but $\displaystyle \mathbb{F}_8$ seemed a bit less "special" and more general!  Reply With Quote

2.

3. $\Bbb F_8$ will have a "medium-large" multiplication table (64 entries) but it's do-able with some patience. Ditto for addition.

The key to creating such a table is finding an irreducible polynomial of degree 4 in $\Bbb Z_2[x]$, and expressing every element of $\Bbb F_8$ as $\Bbb Z_2$-linear combinations of $1,u,u^2,u^3$, where $u$ is a root of the irreducible polynomial you found. This will make the addition table easy.

Now, if you happen to find an element $b \in \Bbb F_8$ of order 7, the multiplication table will be easy. Good luck!

(Hint: try $x^4 + x^3 + x^2 + x + 1$. It clearly has no linear factors...does it have quadratic factors?).  Reply With Quote

4. I think Deveno's example has 16 elements. A model for $\mathbb{F}_8$ is $F := Z_2[x]/(x^3+x+1)$. Letting $u = x + (x^3+x+1)$, we have $u^3 = u + 1$ and we can write

$F = \{0,1,u, u+1,u^2,u^2+1, u^2+u, u^2+u+1\}$.

With this, you can make a table.  Reply With Quote Originally Posted by Deveno $\Bbb F_8$ will have a "medium-large" multiplication table (64 entries) but it's do-able with some patience. Ditto for addition.

The key to creating such a table is finding an irreducible polynomial of degree 4 in $\Bbb Z_2[x]$, and expressing every element of $\Bbb F_8$ as $\Bbb Z_2$-linear combinations of $1,u,u^2,u^3$, where $u$ is a root of the irreducible polynomial you found. This will make the addition table easy.

Now, if you happen to find an element $b \in \Bbb F_8$ of order 7, the multiplication table will be easy. Good luck!

(Hint: try $x^4 + x^3 + x^2 + x + 1$. It clearly has no linear factors...does it have quadratic factors?).

Thanks Deveno  think I get this  BUT, just to be sure:

You write:

"The key to creating such a table is finding an irreducible polynomial of degree 4 in $\Bbb Z_2[x]$, and expressing every element of $\Bbb F_8$ as $\Bbb Z_2$-linear combinations of $1,u,u^2,u^3$, where $u$ is a root of the irreducible polynomial you found."

What is the theorems/logic behind this reasoning?

Peter

- - - Updated - - - Originally Posted by Euge I think Deveno's example has 16 elements. A model for $\mathbb{F}_8$ is $F := Z_2[x]/(x^3+x+1)$. Letting $u = x + (x^3+x+1)$, we have $u^3 = u + 1$ and we can write

$F = \{0,1,u, u+1,u^2,u^2+1, u^2+u, u^2+u+1\}$.

With this, you can make a table.

I guess the logic here is that $\displaystyle \mathbb{F}_8$ is isomorphic to $F := Z_2[x]/(x^3+x+1)$ so that you can use this 'model' to determine/calculate the elements of $\displaystyle \mathbb{F}_8$. Is that correct?

What logic and results/theorems did you use to establish that $F := Z_2[x]/(x^3+x+1)$ was a 'model' for (isomorphic to) $\displaystyle \mathbb{F}_8$?

Peter  Reply With Quote

6. Yes, Peter, I meant $F$ is isomorphic to $\mathbb{F}_8$. I used the fact that the quotient of a commutative ring by a maximal ideal is a field to claim that $F$ is a field. Since $x^3+x+1$ is irreducible over $\mathbb{Z}_2$ (since it doesn't have any roots in $\mathbb{Z}_2$), the ideal $(x^3+x+1)$ is maximal in $\mathbb{Z}_2$. So I can use fact I mentioned to deduce that $F$ is a field.  Reply With Quote Originally Posted by Euge Yes, Peter, I meant $F$ is isomorphic to $\mathbb{F}_8$. I used the fact that the quotient of a commutative ring by a maximal ideal is a field to claim that $F$ is a field. Since $x^3+x+1$ is irreducible over $\mathbb{Z}_2$ (since it doesn't have any roots in $\mathbb{Z}_2$), the ideal $(x^3+x+1)$ is maximal in $\mathbb{Z}_2$. So I can use fact I mentioned to deduce that $F$ is a field.

Thanks Euge  OK, yes  but how did you figure that $\displaystyle \mathbb{Z}_2 {x}/ (x^3 + x + 1}$ had 8 elements  and further, how did you come up with this field in the first place  what mental process did you work though ...

Peter  Reply With Quote

8. To answer both your questions, Peter, let's consider the polynomial ring $\mathbb{Z}_p[x]$, where $p$ is a prime. Let $f(x)$ be any polynomial of degree $n$ in $\mathbb{Z}_p[x]$. Since $pg = 0$ for all $g \in Z_p$, it follows that $pv = 0$ for all $v$ in $\mathbb{Z}_p[x]/(f(x))$. So the factor ring $\mathbb{Z}_p[x]/(f(x))$ has the structure of a vector space over $\mathbb{Z}_p$. You can also see that $\mathbb{Z}_p[x]/(f(x))$ is a $\mathbb{Z}_p$-vector space by observing that it is a module over $\mathbb{Z}_p$ and $\mathbb{Z}_p$ is a field.

Let

$f(x) = a_0 + a_1 x + \cdots + a_n x^n$

where $a_n \neq 0$. If $u = x + (f(x))$, then

$u^n = -(a_0/a_n) - (a_1/a_n)u - \cdots - (a_{n-1}/a_n)u^{n-1}$.

By the division algorithm for polynomials, it follows that every element of $\mathbb{Z}_p[x]/(f(x))$ can be represented uniquely as a polynomial in $\mathbb{Z}_p[u]$ of degree less than $n$. This shows that the set $\{1,u, u^2,\ldots,u^{n-1}\}$ is a $\mathbb{Z}_p$-basis for $\mathbb{Z}_p[x]/(f(x))$. Therefore $\mathbb{Z}_p[x]/(f(x))$ has $|\mathbb{Z}_p|^n = p^n$ elements. Choosing $f(x)$ to be irreducible will make $\mathbb{Z}_p[x]/(f(x))$ a field with $p^n$ elements.

In the special case that $p = 2$ and $f(x) = x^3 + x + 1$, we get the field $F$ with 8 elements.  Reply With Quote

9. Originally Posted by Euge I think Deveno's example has 16 elements. A model for $\mathbb{F}_8$ is $F := Z_2[x]/(x^3+x+1)$. Letting $u = x + (x^3+x+1)$, we have $u^3 = u + 1$ and we can write

$F = \{0,1,u, u+1,u^2,u^2+1, u^2+u, u^2+u+1\}$.

With this, you can make a table.
My bad, for some reason I got $4\cdot 2( = 2^3)$ confused with $2^4$ Originally Posted by Peter Thanks Euge  OK, yes  but how did you figure that $\displaystyle \mathbb{Z}_2[x]/ (x^3 + x + 1}$ had 8 elements  and further, how did you come up with this field in the first place  what mental process did you work though ...

Peter
You only need an irreducible polynomial of the proper degree. For consider, we can write every element in:

$\Bbb Z_2[x]/(x^3 + x + 1)$ as a coset of the form:

$a + bx + cx^2 + (x^3 + x + 1)$

This can be represented as the triple: $(a,b,c)$.

We have two choices for $a$, two choices for $b$, two choices for $c$, giving $2 \cdot 2\cdot 2 = 8$ distinct cosets.

(this is because we can for any polynomial, write:

$p(x) = q(x)(x^3 + x + 1) + r(x)$, where $r(x) = a + bx + cx^2$ (possibly any of $a,b,c$ are 0)).

So we can list the 8 elements of $\Bbb F_8$ as either:

$(0,0,0) \iff 0$
$(1,0,0) \iff 1$
$(0,1,0) \iff u = x + (x^3 + x + 1)$
$(1,1,0) \iff 1+u$
$(0,0,1) \iff u^2$
$(1,0,1) \iff 1+u^2$
$(0,1,1) \iff u+u^2$
$(1,1,1) \iff 1+u+u^2$

**********

Let's try to find an element of order 7.

$u^2 \neq 1$ so $u$ is not order 2.
$u^3 = 1+u$ (since $u^3 + u + 1 = 0$, so $u^3 + (u + u) + (1+1) = u + 1$, and the last two terms on the left are 0).

So $u$ is not of order 3.

$u^4 = u(u^3) = u(1+u) = u+u^2 \neq 1$
$u^5 = u(u^4) = u(u+u^2) = u^2 + u^3 = 1+u+u^2$
$u^6 = u(u^5) = u(1+u+u^2) = u+u^2+u^3 = 1+u+u+u^2 = 1+u^2$
$u^7 = u(u^6) = u(1+u^2) = u+u^3 = 1+u+u = 1$

so $u$ is an element of order 7.

So, for example, to calculate:

$(1+u)(1+u^2) = u^3u^6 = u^9 = u^2$.

We could use $u^3 = 1+u$ to do this, too:

$(1+u)(1+u^2) = (1+u^2) + u(1+u^2) = 1 + u^2 + u + u^3 = 1 + u + u^2 + 1 + u = (1 + 1) + (u + u) + u^2$

$= 0 + 0 + u^2 = u^2$.  Reply With Quote

10. Some other things to consider with finite fields:

Every field has a multiplicative identity, $1$.

It follows that the subgroup of $(F,+)$ for a finite field $F$, generated by $1$ is a finite cyclic group. Thus, $1$ has finite additive order in $F$.

Since this is an abelian group, we have a natural $\Bbb Z$-action:

$\displaystyle k \cdot 1 = \sum_{i = 1}^k 1$, often written as:

$k \cdot 1 = 1 + 1 + \cdots + 1$ ($k$ summands).

Since $\langle 1\rangle$ is cyclic, every element can be written in this form.

This action gives $\langle 1\rangle$ a natural ring multiplication, as:

$(k\cdot 1)(m\cdot 1) = (km)\cdot 1$.

It follows that $\langle 1\rangle \cong \Bbb Z_n$, for some integer $n$ (called the characteristic of $F$).

Now we know $F$ contains no zero-divisors (since all non-zero elements are units, and units are NEVER zero-divisors, and vice versa). Hence our copy of $\Bbb Z_n$ inside $F$ likewise contains no zero-divisors.

Hence, $n$ is prime. For emphasis: EVERY finite field has prime characteristic.

We can thus regard $F$ as an extension of the ring $\Bbb Z_p$, for some prime $p$, and this defines a $\Bbb Z_p$-action on $F$:

$(k \cdot 1)\cdot x = (k\cdot 1)x$ (the multiplication on the right, is that of $F$).

As Euge notes, this means we have a vector space over the field $\Bbb Z_p$.

As this vector space is finite, it must have a finite basis, say: $\{x_1,x_2,\dots,x_n\}$.

This means every element of $F$ is UNIQUELY expressible as:

$a_1x_1 + a_2x_2 +\cdots + a_nx_n$, for $a_1,a_2,\dots,a_n \in \Bbb Z_p$.

Well, we can simply COUNT these elements: there are $p$ choices for each "coefficient" of the $x_j$, which gives us:

$|F| = p^n$.

So every finite field has $p^n$ elements for some prime $p$, and some natural number $n > 0$.

So, for example, there is NO field that has 6 elements, or 12, or 15.

One might wonder...well, how many fields of order $p^n$ are there? The answer is rather startling: exactly one (up to isomorphism).

Not only is every finite field of order $p^n$, but for every $p$ and every $n$, there IS a field of that order, and every other field of that order is isomorphic to it.

There is another surprising fact about finite fields: the multiplicative group of a finite field is CYCLIC.

Finite fields have a simple subfield structure: for example, a finite field of order 16, has a very simple lattice of subfields:

$\Bbb F_{16} - \Bbb F_8 - \Bbb F_2$.

At this point you might want to hazard a guess about what the group $\text{Gal}(\Bbb F_{16}/\Bbb F_2)$ looks like, and try to conjecture what polynomial in $\Bbb F_2[x]$ that $\Bbb F_{16}$ might be the splitting field of.  Reply With Quote Originally Posted by Euge To answer both your questions, Peter, let's consider the polynomial ring $\mathbb{Z}_p[x]$, where $p$ is a prime. Let $f(x)$ be any polynomial of degree $n$ in $\mathbb{Z}_p[x]$. Since $pg = 0$ for all $g \in Z_p$, it follows that $pv = 0$ for all $v$ in $\mathbb{Z}_p[x]/(f(x))$. So the factor ring $\mathbb{Z}_p[x]/(f(x))$ has the structure of a vector space over $\mathbb{Z}_p$. You can also see that $\mathbb{Z}_p[x]/(f(x))$ is a $\mathbb{Z}_p$-vector space by observing that it is a module over $\mathbb{Z}_p$ and $\mathbb{Z}_p$ is a field.

Let

$f(x) = a_0 + a_1 x + \cdots + a_n x^n$

where $a_n \neq 0$. If $u = x + (f(x))$, then

$u^n = -(a_0/a_n) - (a_1/a_n)u - \cdots - (a_{n-1}/a_n)u^{n-1}$.

By the division algorithm for polynomials, it follows that every element of $\mathbb{Z}_p[x]/(f(x))$ can be represented uniquely as a polynomial in $\mathbb{Z}_p[u]$ of degree less than $n$. This shows that the set $\{1,u, u^2,\ldots,u^{n-1}\}$ is a $\mathbb{Z}_p$-basis for $\mathbb{Z}_p[x]/(f(x))$. Therefore $\mathbb{Z}_p[x]/(f(x))$ has $|\mathbb{Z}_p|^n = p^n$ elements. Choosing $f(x)$ to be irreducible will make $\mathbb{Z}_p[x]/(f(x))$ a field with $p^n$ elements.

In the special case that $p = 2$ and $f(x) = x^3 + x + 1$, we get the field $F$ with 8 elements.
Thanks Euge  most helpful  a most important piece of logic for me was when you write:

"This shows that the set $\{1,u, u^2,\ldots,u^{n-1}\}$ is a $\mathbb{Z}_p$-basis for $\mathbb{Z}_p[x]/(f(x))$. Therefore $\mathbb{Z}_p[x]/(f(x))$ has $|\mathbb{Z}_p|^n = p^n$ elements. Choosing $f(x)$ to be irreducible will make $\mathbb{Z}_p[x]/(f(x))$ a field with $p^n$ elements. "

This links the degree of the minimal polynomial and the number of elements in $\displaystyle \mathbb{Z}_p$ to the number of elements in the field of interest  previously I was missing that link!  ...

Thanks again,

Peter  Reply With Quote

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
• 