# Thread: Abstract Algebra - Primitive Roots for Polynomials

1. ## Abstract Algebra - Primitive Roots for Polynomials

The ﬁeld GF(8) of 8 elements can be thought of as consisting of elements of the form a*x^2 + bx + c, where a, b, c ∈ Z2.

(Thus, all coeﬃcients are simpliﬁed mod 2.)

Moreover, x^3 = x + 1.

(a) Compute (x^2 + x + 1) + (x^2 + 1), simplifying your answer to the form a*x^2 + bx + c for a, b, c ∈ Z2.

(b) Compute (x^2 + 1) * (x + 1), simplifying your answer to the form a*x^2 + bx + c for a, b, c ∈ Z2.

(c) Show that x is a primitive root by computing the powers x^k for k = 3,4, . . .7, simplifying your answers to the form a*x^2 + bx + c for a, b, c ∈ Z2. (This shows that <x> is cyclic of order 7.)

(d) Compute (x^2 + 1)−1, simplifying your answer to the form a*x^2 + bx + c for a, b, c ∈ Z2. (Hint: Use the result of (c) to represent x^2 + 1 as a power of x. Then simplify (x^2 + 1)−1 using rules for powers, then look up the answer using the computation you did in (c).)

Remark. You can use the ax2 + bx + c to add elements of GF(8), because it’s just a matter of adding coeﬃcients and reducing mod 2. On the other hand, you can multiply elements by representing them as powers of x and using rules for powers, translating back to ax2 + bx + c by using (c) if needed.

This is what I have so far:

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

(b) (x^2 + 1) * (x + 1) = x^3 + x^2 + x + 1 = (x + 1) + x^2 + x + 1 = x^2 + 2x + 2 = x^2

Then for part (c) I get lost about how to show that x is a primitive root.

2. ## Re: Abstract Algebra - Primitive Roots for Polynomials

Actually I figured out part c. This is what I have:

x^3 = x + 1

x^4 = x*x^3 = x*(x + 1) = x^2 + x

x^5 = x*x^4 = x*(x^2 + x) = x^3 + x^2 = x^2 + x + 1

x^6 = x*x^5 = x*(x^2 + x + 1) = x^3 + x^2 + x = (x + 1) + x^2 + x = x^2 + 2x + 1 = x^2 + 1

x^7 = x*x^6 = x*(x^2 + 1) = x^3 + x = (x + 1) + x = 2x + 1 = 1

So,

<x> = { x + 1, x^2 + x, x^2 + x + 1, x^2 + 1, 1 }

3. ## Re: Abstract Algebra - Primitive Roots for Polynomials

$x^3 = x+1$

$x^4 = x\cdot x^3 = x(x+1) = x^2+x$

$x^5 = x\cdot x^4 = x(x^2+x) = x^3+x^2 = x^2+x+1$

$x^6 = x\cdot x^5 = x(x^2+x+1) = x^3+x^2+x = x^2+1$

$x^7 = x\cdot x^6 = x(x^2+1) = x^3+x = 1$

Hence, $x^8 = x$.

Thus, ${<x>} = \{1,x,x^2,x+1,x^2+x,x^2+x+1,x^2+1\}$

4. ## Re: Abstract Algebra - Primitive Roots for Polynomials

For part (d) would this be correct:

(x^2 + 1)^(-1) = (x^6)^(-1) = x^(-6) = x^0 (mod 2) = 1

5. ## Re: Abstract Algebra - Primitive Roots for Polynomials

Originally Posted by AwesomeHedgehog
For part (d) would this be correct:

(x^2 + 1)^(-1) = (x^6)^(-1) = x^(-6) = x^0 (mod 2) = 1
No, that is not correct.

$1 = x^7 = x^6\cdot x$

Multiplying both sides by $x^{-6}$ on the left gives $x^{-6}\cdot 1 = x^{-6}\cdot x^6\cdot x = 1\cdot x = x$. So, $x^{-6} = x$.