Aufgaben:Exercise 2.1: Group, Ring, Field

• Return to book

"Addition" and "Multiplication"
    for  $q = 3$  and  $q = 4$.

In the  "theory section"  to this chapter,  various algebraic terms were defined.  For what follows,  we assume that all sets consist of  $q$  elements each,  where here either  $q = 3$  or  $q = 4$.  Then holds:

• An  "algebraic group"  is a finite set  $G = \{0, \, 1, \hspace{0.05cm}\text{...} \hspace{0.1cm} , \ q-1\}$  together with a linking rule defined between all elements.  An  "additive group"  is denoted by  $(G, \ +)$,  a multiplicative one by  $(G, \ \cdot)$.

• An  "algebraic ring"  denotes a set  $R = \{0, \, 1, \hspace{0.05cm}\text{...} \hspace{0.1cm} , \ q-1\}$  together with two arithmetic operations defined therein,  namely addition  ("$+$")  and multiplication  ("$\hspace{0.05cm}\cdot\hspace{0.05cm}$").

• An  "algebraic field"  is a ring where division is additionally allowed and the commutative law is satisfied.

Since we consider here finite sets only,  a  "field"  is at the same time a  "Galois field"  ${\rm GF}(q)$  of order  $q$.

An essential property of the Galois field  ${\rm GF}(q) = \{\hspace{0.1cm}z_0,\hspace{0.1cm} z_1,\hspace{0.05cm}\text{...} \hspace{0.1cm} , \hspace{0.1cm}z_{q-1}\}$  is that it has at least one primitive element:  An element  $z_i ≠ 0$  is said to be  "primitive"  if the following condition is satisfied  $(k$  is an integer$)$:

$$z_i^k \hspace{0.15cm}{\rm mod}\hspace{0.15cm}q = \left\{ \begin{array}{c} \ne 1\\ 1 \end{array} \right.\quad \begin{array}{*{1}c} {\rm for} \hspace{0.15cm}1 \le k < q-1 \\ {\rm for} \hspace{0.15cm}k = q-1 \\ \end{array} \hspace{0.35cm} \Rightarrow \hspace{0.35cm} z_i \hspace{0.15cm}{\rm is \hspace{0.15cm}a\hspace{0.15cm} primitive \hspace{0.15cm}element} \hspace{0.05cm}. $$

Only for a primitive element  $z_i$ 

• the arithmetic oparation  $z_i^k$  $($with  $k = 1, \, 2, \, 3, \, \hspace{0.05cm}\text{...} )$  yields all elements of the Galois field
• except the zero element $z_0 = 0$.

Hints:

• The exercise covers the topic of the chapter  "Some basics of algebra".

• Note that for group, ring and field with each  $q$  elements,  the arithmetic operations  "$+$"  and  "$\hspace{0.05cm}\cdot\hspace{0.05cm}$"  are to be understood modulo  $q$.

Questions

1

Which of the given tables describe a  group?

	Table  $\rm A3$,
	Table  $\rm M3$,
	Table  $\rm A3$  and table  $\rm M3$  together,
	Table  $\rm A4$  and table  $\rm M4$  together.

2

Which of the given tables describe a  ring?

	Table  $\rm A3$,
	Table  $\rm M3$,
	Table  $\rm A3$  and table  $\rm M3$  together,
	table  $\rm A4$  and table  $\rm M4$  together,
	Table  $\rm A3$  and table  $\rm M4$  together.

3

Which of the tables describe a  (Galois) field?

	Table  $\rm A3$,
	Table  $\rm M3$,
	Table  $\rm A3$  and table  $\rm M3$  together,
	Table  $\rm A4$  and table  $\rm M4$  together.

4

Which elements of the set  $\{0, \, 1, \, 2\} \ \Rightarrow \ q = 3$  are  "primitive"?

	$z_0 = 0$,
	$z_1 = 1$,
	$z_2 = 2.$

5

Which elements of the set  $\{0, \, 1, \, 2, \, 3\} \ \Rightarrow \ q = 4$  are  "primitive"?

	$z_0 = 0$,
	$z_1 = 1$,
	$z_2 = 2$,
	$z_3 = 3$.

Solution

Solution

(1)  With the number set  $Z_3 = \{0, \, 1, \, 2\}$  describes

• the table A3 the additive group  $(Z_3, \, +)$,
• the table M3 the multiplicative group  $(Z_3, \, \cdot)$.

⇒   Solution suggestion 1 and 2. 

The solution suggestions 3 and 4 do not apply here,  because only one arithmetic operation  (addition or multiplication)  is defined for each group.

(2)  On an algebraic ring,  in contrast,  two arithmetic operations are defined.  Thus,  the  proposed solutions 3 and 4  are correct:

• Tables A3 and M3 describe together the ring  $(Z_3, \, +, \, \cdot)$.
• Tables A4 and M4 describe together the ring  $(Z_4, \, +, \, \cdot)$.

In contrast,  A3 and M4 do not describe a ring because they refer to different quantities.

(3)  Every field is also a ring,  but not every ring is also a field:

• For the latter,  division is also defined and for each element there is also the  multiplicative inverse.
• A  finite number ring  of order  $q$  (that is,  with  $q$  elements)  is a field only if  $q$  is a prime number.
• This is then also called a Galois field  ${\rm GF}(q)$.

So the correct answer is  answer 3:

• The arithmetic operations according to tables A3 and M3 together result in the Galois field  ${\rm GF}(3)$.
• In contrast,  tables A4 (addition) and M4 multiplication) together with the set  $\{0, \, 1, \, 2, \, 3\}$  do not result in the Galois field  ${\rm GF}(4)$.
• A condition for a Galois field is that for each element  $z_i$  there exists a multiplicative inverse  ${\rm Inv}_{\rm M}{(z_i)}$  such that the equation  $z_i \cdot {\rm Inv}_{\rm M}(z_i) = 1$  is satisfied.
• According to table M4,  however, $\rm Inv_M(2)$  does not exist.  There is no  "$1$"  in the third row.

For example,  a Galois field  $\rm GF(4)$  is obtained by extending the binary set  $\{0, \, 1\}$  to the set  $\{0, \, 1, \, \alpha, \, 1+\alpha\}$.  For more details, see the page  "Example of an extension field" page.

(4)  The zero element is never a primitive element.  Also  $z_1 = 1$  is not a primitive element,  because then with  $q = 3$  would have to hold:

$$z_1^1 \hspace{0.15cm}{\rm mod\hspace{0.15cm}} 3\hspace{0.1cm} \ne 1 \hspace{0.05cm},\hspace{0.3cm}z_1^2 \hspace{0.15cm}{\rm mod\hspace{0.15cm}} 3\hspace{0.1cm} = 1 \hspace{0.05cm}.$$

On the other hand,  $z_2 = 2$  is a primitive element because of

$$2^1 \hspace{0.15cm}{\rm mod\hspace{0.15cm}} 3\hspace{0.1cm} = 2 \hspace{0.05cm},\hspace{0.3cm}2^2 \hspace{0.15cm}{\rm mod\hspace{0.15cm}} 3\hspace{0.1cm} = 1 \hspace{0.05cm}.$$

The correct solution is  solution suggestion 3.

(5)  The set  $\{0, \, 1, \, 2, \, 3\}$  has no primitive element and accordingly does not satisfy the requirements of a Galois field:

$$z_1 \hspace{-0.1cm} \ = \ \hspace{-0.1cm} 1\text{:}\hspace{0.35cm} 1^1 = 1\hspace{0.05cm},\hspace{0.1cm}1^2 = 1\hspace{0.05cm},\hspace{0.1cm}1^3 = 1\hspace{0.05cm},$$

$$z_2 \hspace{-0.1cm} \ = \ \hspace{-0.1cm} 2\text{:}\hspace{0.35cm} 2^1 = 2\hspace{0.05cm},\hspace{0.1cm}2^2 \hspace{0.15cm}{\rm mod}\hspace{0.15cm}4 = 0 \hspace{0.05cm},\hspace{0.1cm}2^3 \hspace{0.15cm}{\rm mod}\hspace{0.15cm}4 = 0\hspace{0.05cm},$$

$$z_3 \hspace{-0.1cm} \ = \ \hspace{-0.1cm} 3\text{:}\hspace{0.35cm} 3^1 = 3\hspace{0.05cm},\hspace{0.1cm}3^2 \hspace{0.15cm}{\rm mod}\hspace{0.15cm}4 = 1 \hspace{0.05cm},\hspace{0.1cm}3^3 \hspace{0.15cm}{\rm mod}\hspace{0.15cm}4 = 3\hspace{0.05cm}.$$