Primitive root in a finite field

Printable View

September 23rd 2011, 11:18 AM
uberbandgeek6

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.
September 23rd 2011, 02:41 PM
Drexel28

Re: Primitive root in a finite field

Quote:

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|$ ?
September 23rd 2011, 05:21 PM
uberbandgeek6

Re: Primitive root in a finite field

I'm sorry, but I don't really understand what you mean by |r^s| and |r|.
September 23rd 2011, 06:12 PM
Drexel28

Re: Primitive root in a finite field

Quote:

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?
September 24th 2011, 03:23 PM
uberbandgeek6

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.
September 28th 2011, 01:14 AM
Deveno

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).
September 28th 2011, 10:41 AM
uberbandgeek6

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?
September 28th 2011, 04:42 PM
Deveno

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