
MHB Master
#1
July 19th, 2014,
20:58
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!
Last edited by Peter; July 19th, 2014 at 21:21.

July 19th, 2014 20:58
# ADS
Circuit advertisement

MHB Master
#2
July 19th, 2014,
21:50
$\Bbb F_8$ will have a "mediumlarge" multiplication table (64 entries) but it's doable 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?).

MHB Master
#3
July 19th, 2014,
22:31
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.

MHB Master
#4
July 19th, 2014,
23:17
Thread Author
Originally Posted by
Deveno
$\Bbb F_8$ will have a "mediumlarge" multiplication table (64 entries) but it's doable 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 $?
Thanks again for your help.
Peter

MHB Master
#5
July 19th, 2014,
23:39
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.

MHB Master
#6
July 20th, 2014,
00:23
Thread Author
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

MHB Master
#7
July 20th, 2014,
02:04
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_{n1}/a_n)u^{n1}$.
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^{n1}\}$ 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.
Last edited by Euge; July 20th, 2014 at 02:16.

MHB Master
#8
July 20th, 2014,
02:28
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$.

MHB Master
#9
July 20th, 2014,
03:02
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 zerodivisors (since all nonzero elements are units, and units are NEVER zerodivisors, and vice versa). Hence our copy of $\Bbb Z_n$ inside $F$ likewise contains no zerodivisors.
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.
Last edited by Deveno; July 28th, 2014 at 02:07.

MHB Master
#10
July 20th, 2014,
23:56
Thread Author
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_{n1}/a_n)u^{n1}$.
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^{n1}\}$ 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^{n1}\}$ 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