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