Exercise 2.47 on Page 114: Showing a Polynomial Has Root in \mathbb{F}_4 - Peter

[Math Amateur]

I am reading Chapter 2: Commutative Rings in Joseph Rotman's book, Advanced Modern Algebra (Second Edition).

I need help with Exercise 2.47 on page 114.

Problem 2.47 reads as follows:

View attachment 2692I need help with showing that \(\displaystyle f(x)\) has a root \(\displaystyle \alpha \in \mathbb{F}_4 \).

My work on this part of the problem is as follows:

The elements of \(\displaystyle \mathbb{F}_4 \) are 0, 1, 2 and 3.

Now we proceed as follows:

\(\displaystyle f(0) = 0^2 + 0 + 1 = 1_4 \ne 0_4 \)
\(\displaystyle \Longrightarrow 0_4 \) is not a root of \(\displaystyle f(x)\) in \(\displaystyle \mathbb{F}_4 \)

\(\displaystyle f(1) = 1^2 + 1 + 1 = 3_4 \ne 0_4 \)
\(\displaystyle \Longrightarrow 1_4 \) is not a root of \(\displaystyle f(x)\) in \(\displaystyle \mathbb{F}_4 \)

\(\displaystyle f(2) = 2^2 + 2 + 1 = 7_4 \ne 0_4 \)
\(\displaystyle \Longrightarrow 2_4 \) is not a root of \(\displaystyle f(x)\) in \(\displaystyle \mathbb{F}_4 \)

\(\displaystyle f(3) = 3^2 + 3 + 1 = 13_4 \ne 0_4 \)
\(\displaystyle \Longrightarrow 3_4 \) is not a root of \(\displaystyle f(x)\) in \(\displaystyle \mathbb{F}_4 \)

... ... BUT I seem to have shown (wrongly I'm sure!) that f(x) has no root in \(\displaystyle \mathbb{F}_4 \)?

Can someone please help me with this issue?

Peter

 

[Deveno]

Uh..."2" and "3" DO NOT EXIST in $\Bbb F_4$.

The elements of $\Bbb F_4$ can be written as $0,1,a,a+1$ or: (using vector notation) as $(0,0),(1,0),(0,1),(1,1)$.

Let's use the former to show that $a$ is a root of $x^2 + x + 1$.

As you may recall from a prior post, we have:

$a^2 = a\cdot a = a+1$.

Thus:

$a^2 + a + 1 = (a + 1) + (a + 1) = (1 + 1)(a + 1) = 0(a + 1) = 0$.

In fact, $a + 1$ is the "other root":

$(a + 1)^2 + (a + 1) + 1 = (a + 1)(a + 1) + (a + 1) + 1 = (a + 1 + 1)(a + 1) + 1$

$= (a)(a + 1) + 1 = a^2 + a + 1 = 0$ (by the above).

Indeed:

$(x - a)(x - (a + 1)) = (x + a)(x + (a + 1))$ (since $\Bbb F_4$ has characteristic 2)

$= x^2 + x(a + 1) + ax + a(a + 1) = x^2 + (a + 1 + a)x + a^2 + a$

$= x^2 + ((a + a) + 1)x - 1 = x^2 + ((1 + 1)a + 1)x + 1$ (remember, $1 = -1$)

$= x^2 + (0a + 1)x + 1 = x^2 + x + 1$.

*************

The 4-element field is NOT $\Bbb Z_4$, which is NOT a field, because it has ZERO DIVISORS (zero divisors cannot have inverses, but they ARE non-zero, and in a field EVERY non-zero element HAS to have an inverse).

Explicitly:

$[2]_4 \cdot [2]_4 = [0]_4$, but $[2]_4 \neq [0]_4$.

 

[Math Amateur]

Uh..."2" and "3" DO NOT EXIST in $\Bbb F_4$.

The elements of $\Bbb F_4$ can be written as $0,1,a,a+1$ or: (using vector notation) as $(0,0),(1,0),(0,1),(1,1)$.

Let's use the former to show that $a$ is a root of $x^2 + x + 1$.

As you may recall from a prior post, we have:

$a^2 = a\cdot a = a+1$.

Thus:

$a^2 + a + 1 = (a + 1) + (a + 1) = (1 + 1)(a + 1) = 0(a + 1) = 0$.

In fact, $a + 1$ is the "other root":

$(a + 1)^2 + (a + 1) + 1 = (a + 1)(a + 1) + (a + 1) + 1 = (a + 1 + 1)(a + 1) + 1$

$= (a)(a + 1) + 1 = a^2 + a + 1 = 0$ (by the above).

Indeed:

$(x - a)(x - (a + 1)) = (x + a)(x + (a + 1))$ (since $\Bbb F_4$ has characteristic 2)

$= x^2 + x(a + 1) + ax + a(a + 1) = x^2 + (a + 1 + a)x + a^2 + a$

$= x^2 + ((a + a) + 1)x - 1 = x^2 + ((1 + 1)a + 1)x + 1$ (remember, $1 = -1$)

$= x^2 + (0a + 1)x + 1 = x^2 + x + 1$.

*************

The 4-element field is NOT $\Bbb Z_4$, which is NOT a field, because it has ZERO DIVISORS (zero divisors cannot have inverses, but they ARE non-zero, and in a field EVERY non-zero element HAS to have an inverse).

Explicitly:

$[2]_4 \cdot [2]_4 = [0]_4$, but $[2]_4 \neq [0]_4$.

Thanks for the help Deveno ... ... I certainly need to get a better understanding of finite fields ...

Peter

 

[Deveno]

There are 3 main ways to look at a finite field.

The first way is to focus on the addition. The first thing that one can show is that the subgroup of $(F,+)$ generated by $1$ is ALSO a field, called the PRIME FIELD of $F$. There is a reason for the name "prime":

$\langle 1\rangle \cong \Bbb Z_n$ for some natural number $n$, this number is called the CHARACTERISTIC of the field.

Since $\Bbb Z_n$ forms a ring under multiplication, we see that $\langle 1\rangle$ forms a sub-ring of $F$. Let's call this ring $P$.

Now every non-zero element of $P$ is a unit (since this is true of $F$). This tells us something special about $n$: it must be prime. Why?

Well, if $n = ab$, for positive integers $1 < a,b < n$, we have:

$(a1)(b1) = (ab)1 = n1 = 0$, so $a1 \neq 0 \in F$ is a zero-divisor. But $F$, being a field HAS no zero-divisors. This means $n$ cannot be composite, and $n = 1$ is not a possibility, since in a field, $0 \neq 1$.

So $P \cong \Bbb Z_p$, for some prime $p$. And this is a field.

Now $F$ can be made into a $P$-module in a natural way- define, for $a \in P$, and $x \in F$:

$a\cdot x = ax$, where the RHS is the multiplication in $F$.

Since $P$ is itself a field, $F$ is a $P$-vector space. If we choose a basis: $\{x_1,x_2,\dots,x_n\}$, it is clear we get:

$|P|^n = p^n$ distinct vectors in $F$, that is: $|F| = p^n$, where $n$ is the cardinality of the basis.

In this view, addition is trivial: we just "add the coordinates". Multiplication, however, is somewhat of a mystery.

The second way is to focus on the multiplicative group: it turns out that the multiplicative group of a finite field is CYCLIC, and therefore has a generator (called a PRIMITIVE, or primitive element). Now the multiplication is trivial, but addition is brutal.

The third way ties the two together: We start with the ring $Z_p[x]$, and choose an irreducible polynomial $f(x)$ of degree $n$. It is clear, then, that $Z_p[x]/(f(x))$ is a finite field with $p^n$ cosets. In fact, ALL finite fields arise this way. This allows us to express elements of this field as "polynomials in $u$", where $u$ is a root of $f(x)$ (which corresponds to the coset $x + (f(x))$).

 

[Math Amateur]

There are 3 main ways to look at a finite field.

The first way is to focus on the addition. The first thing that one can show is that the subgroup of $(F,+)$ generated by $1$ is ALSO a field, called the PRIME FIELD of $F$. There is a reason for the name "prime":

$\langle 1\rangle \cong \Bbb Z_n$ for some natural number $n$, this number is called the CHARACTERISTIC of the field.

Since $\Bbb Z_n$ forms a ring under multiplication, we see that $\langle 1\rangle$ forms a sub-ring of $F$. Let's call this ring $P$.

Now every non-zero element of $P$ is a unit (since this is true of $F$). This tells us something special about $n$: it must be prime. Why?

Well, if $n = ab$, for positive integers $1 < a,b < n$, we have:

$(a1)(b1) = (ab)1 = n1 = 0$, so $a1 \neq 0 \in F$ is a zero-divisor. But $F$, being a field HAS no zero-divisors. This means $n$ cannot be composite, and $n = 1$ is not a possibility, since in a field, $0 \neq 1$.

So $P \cong \Bbb Z_p$, for some prime $p$. And this is a field.

Now $F$ can be made into a $P$-module in a natural way- define, for $a \in P$, and $x \in F$:

$a\cdot x = ax$, where the RHS is the multiplication in $F$.

Since $P$ is itself a field, $F$ is a $P$-vector space. If we choose a basis: $\{x_1,x_2,\dots,x_n\}$, it is clear we get:

$|P|^n = p^n$ distinct vectors in $F$, that is: $|F| = p^n$, where $n$ is the cardinality of the basis.

In this view, addition is trivial: we just "add the coordinates". Multiplication, however, is somewhat of a mystery.

The second way is to focus on the multiplicative group: it turns out that the multiplicative group of a finite field is CYCLIC, and therefore has a generator (called a PRIMITIVE, or primitive element). Now the multiplication is trivial, but addition is brutal.

The third way ties the two together: We start with the ring $Z_p[x]$, and choose an irreducible polynomial $f(x)$ of degree $n$. It is clear, then, that $Z_p[x]/(f(x))$ is a finite field with $p^n$ cosets. In fact, ALL finite fields arise this way. This allows us to express elements of this field as "polynomials in $u$", where $u$ is a root of $f(x)$ (which corresponds to the coset $x + (f(x))$).

Thanks so much Deveno ... ... Really great overview/tutorial on finite fields ... Just working through it carefully now ... ...

Peter