Results 1 to 5 of 5

Math Help - Abstract Algebra - Primitive Roots for Polynomials

  1. #1
    Member
    Joined
    Nov 2013
    From
    Philadelphia
    Posts
    157

    Abstract Algebra - Primitive Roots for Polynomials

    The field 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 coefficients are simplified 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 coefficients 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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Nov 2013
    From
    Philadelphia
    Posts
    157

    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 }
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,857
    Thanks
    720

    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\}$
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Nov 2013
    From
    Philadelphia
    Posts
    157

    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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,857
    Thanks
    720

    Re: Abstract Algebra - Primitive Roots for Polynomials

    Quote Originally Posted by AwesomeHedgehog View Post
    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$.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Primitive roots
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: July 10th 2011, 05:15 PM
  2. Replies: 4
    Last Post: January 10th 2011, 08:51 AM
  3. Replies: 2
    Last Post: December 18th 2009, 12:48 PM
  4. Primitive Roots
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: November 17th 2008, 08:09 PM
  5. Primitive Roots
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: October 15th 2008, 06:58 PM

Search Tags


/mathhelpforum @mathhelpforum