# Thread: Primitive root in a finite field

1. ## 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.

2. ## Re: Primitive root in a finite field

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 $r^s$ generates $\mathbb{F}_q$, so what is the formula for $|r^s|$ in terms of $|r|$?

3. ## Re: Primitive root in a finite field

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

4. ## Re: Primitive root in a finite field

Originally Posted by uberbandgeek6
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?

5. ## 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.

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

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

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