Thread: 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.

Originally Posted by uberbandgeek6

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 generates , so what is the formula for in terms of ?

I'm sorry, but I don't really understand what you mean by |r^s| and |r|.

Originally Posted by uberbandgeek6

I'm sorry, but I don't really understand what you mean by |r^s| and |r|.

Primitive roots in are precisely the generators of , which is equivalent to where denotes the multiplicative order. Make more sense?

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.

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).

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?

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)?