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!

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?).

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.

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.
Thanks Euge … appreciate your help!

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

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.

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

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.

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$.

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.

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

Posting Permissions

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