Results 1 to 8 of 8

Math Help - Primitive root in a finite field

  1. #1
    Member
    Joined
    Sep 2008
    Posts
    79

    Primitive root in a finite field

    We know every finite field F of size q = p^n has a primitive root r (an element whose powers give all the nonzero elements of the field). Prove that r^s is another primitive root, where s has no factor in common with p^n - 1.

    ____

    Okay, I'm not sure where to begin here. I guess since s and p^n - 1 don't have common factors, their gcd must be 1 = a*s + b*(p^n - 1) for some a and b, but this doesn't seem to go anywhere. We haven't technically learned anything like Euler's Totient function yet in class, so I can use that.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21

    Re: Primitive root in a finite field

    Quote Originally Posted by uberbandgeek6 View Post
    We know every finite field F of size q = p^n has a primitive root r (an element whose powers give all the nonzero elements of the field). Prove that r^s is another primitive root, where s has no factor in common with p^n - 1.

    ____

    Okay, I'm not sure where to begin here. I guess since s and p^n - 1 don't have common factors, their gcd must be 1 = a*s + b*(p^n - 1) for some a and b, but this doesn't seem to go anywhere. We haven't technically learned anything like Euler's Totient function yet in class, so I can use that.
    Well, you need to prove that r^s generates \mathbb{F}_q, so what is the formula for |r^s| in terms of |r|?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Sep 2008
    Posts
    79

    Re: Primitive root in a finite field

    I'm sorry, but I don't really understand what you mean by |r^s| and |r|.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21

    Re: Primitive root in a finite field

    Quote Originally Posted by uberbandgeek6 View Post
    I'm sorry, but I don't really understand what you mean by |r^s| and |r|.
    Primitive roots in \mathbb{Z}_n are precisely the generators of \left(\mathbb{Z}_n\right)^\times, which is equivalent to |g|=\varphi(n) where |\cdot| denotes the multiplicative order. Make more sense?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Sep 2008
    Posts
    79

    Re: Primitive root in a finite field

    We have not technically learned about multiplicative order or Euler's totient function yet in class, so I can't use that for the problem. As a hint, we were told that this is "a cyclic group question", but I'm not sure how to use that either.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,391
    Thanks
    757

    Re: Primitive root in a finite field

    hopefully, you know that the group (F*, .) is cyclic.

    now, in a cyclic group, which powers of a generator generate the group?

    (there is a certain relationship between these exponents and the order of the group).
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Sep 2008
    Posts
    79

    Re: Primitive root in a finite field

    Okay, I'm trying to prove this by contradiction. For primitive root r, assume that r^s is also a primitive root, but s has a factor in common with p^n - 1. Since r is a primitive root, I know r, r^2, ..., r^(p^n - 1) should give a rearrangement of the nonzero elements in the finite field.

    Now I'll look at (r^s), (r^s)^2, ..., (r^s)^(p^n - 1). I need to somehow show that this is not a rearrangement of all of the nonzero elements in the finite field. How can I do this?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,391
    Thanks
    757

    Re: Primitive root in a finite field

    the key is to look at the common factor d of s and p^n - 1. can you see why we can pick some 1 < d < p^n - 1?

    we have s = dk, p^n - 1 = dt, for integers k,t. it should be obvious (it may not be to you, if so, think about it for a while) that 1 < t < p^n - 1.

    what is (r^s)^t? how does this show r^s is not a generator (hint: what is the size of a finite cyclic group generated by an element a)?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Splitting Field of a Polynomial over a Finite Field
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: April 1st 2011, 03:45 PM
  2. Replies: 1
    Last Post: February 27th 2011, 05:59 PM
  3. primitive root
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 8th 2010, 08:49 AM
  4. Primitive root in quadratic field
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: April 30th 2008, 01:39 PM
  5. primitive root
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 30th 2006, 02:21 PM

Search Tags


/mathhelpforum @mathhelpforum