# Primitive polynomials

1. Aug 17, 2008

### the_fox

Can anyone tell me how to find the exact number of primitive polynomials of degree n over a finite field F_q? I believe the answer is φ(q^n-1)/n, but I cannot find a proof of this.

2. Aug 17, 2008

### morphism

What's your definition of a primitive polynomial of degree n?

3. Aug 17, 2008

### the_fox

It's an irreducible polynomial whose roots generate F_q^n. So for example f(x)=x^4 + x^3 + x^2 +x + 1 in F_16[x] is not primitive (a root c of f(x) has order 5), while g(x)=x^4 + x + 1 is (a root c of g(x) has necessarily order 15).

4. Aug 17, 2008

### morphism

OK. And do you know how to many generators F_q^n has?

5. Aug 17, 2008

### the_fox

Yeah, φ(q^n-1).

6. Aug 17, 2008

### morphism

Now put 2 and 2 together. (Some field theory will be helpful.)

7. Aug 17, 2008

### the_fox

Every primitive polynomial produces n distinct roots in the extension field that are primitive elements. Hence #(primitive polynomials)*n=φ(q^n-1). But is this a formal argument? I don't feel so much at ease with field theory..

P.S. 2+2=4

8. Aug 17, 2008

### morphism

Yes, that's a formal argument, provided you also note that every generator of F_q^n corresponds to a primitive polynomial of degree n in F_q[x] (namely its minimal polynomial).

9. Aug 18, 2008

### the_fox

Allright. So we can say that elements of order q^n-1 in GL(n,q) can be divided in φ(q^n-1) conjugacy classes, to combine results with the Singer cycles thread. What I want to do is find the order of each conjugacy class. Any ideas?

10. Aug 18, 2008

### morphism

What's the reasoning behind that?

11. Aug 18, 2008

### the_fox

I'm sorry; I meant φ(q^n-1)/n classes. the companion matrices that correspond to primitive polynomials of degree n have order q^n-1 and Singer cycles that have the same minimal polynomial necessarily lie in the same conjugacy class.

12. Aug 18, 2008

### morphism

Is that obvious? I mean, there are two notions of 'conjugacy' here: conjugacy in the sense of field theory in F_q^n, and conjugacy in the sense of group theory in GL(n,q). Do they coincide?

13. Aug 18, 2008

### the_fox

I think it becomes obvious if you notice that a Singer cycle cannot have an irreducible polynomial that is not primitive as a minimal polynomial. For example, can f(x)=x^4 + x^3 + x^2 +x + 1 in F_16[x] be the minimal polynomial of a singer cycle in GL(4,2)?

14. Aug 19, 2008

### the_fox

By the way, I think it's true that no element in GL(n,q) has order that exceeds q^n-1. An thoughts on this?

15. Aug 19, 2008

### morphism

I think this is proved in the paper I posted in the Singer cycle thread.

True, but how does this relate to conjugacy?

16. Aug 19, 2008

### the_fox

What I mean is, that Singer cycles with the same minimal polynomial belong to the same conjugacy class defined by C(m(x)), the companion matrix of m(x). Assume conjugacy is restricted to the group theoretic sense. For example, all Singer cycles in GL(3,2) belong to either one of the two distinct conjugacy classes defined by companion matrices of the irreducible (and also primitive) polynomials x^3+x^2+1 and x^3+x+1.

17. Aug 20, 2008

### the_fox

I just realized that S. cycles are also self centralizing, but I can't prove it. If I manage to though, I will have a formula for how many there are.

18. Aug 20, 2008

### Hurkyl

Staff Emeritus
Let A be an element of GL(n, q).
Let f(x) be the minimal polynomial of A.
Let $f_d(x)$ be the product of all irreducible degree-d factors of f(x).
Note that the $f_d(x)$ are pairwise relatively prime.
Note that $f_d(x)$ divides $x^{q^d - 1} - 1$.
Therefore, f(x) divides the least common multiple of the relevant $x^{q^d - 1} - 1$.
$$\mathop{lcm}\left\{ x^{q^{d_i} - 1} - 1 \right\} = x^{ \mathop{lcm}\{ q^{d_i} - 1 \} }- 1$$
Since $\sum_i d_i \leq n$, we have that $A^m = I$ for some $0 < m < q^n$.

Last edited: Aug 20, 2008
19. Aug 20, 2008

### the_fox

I've also noticed that s.c. commute only with their powers, i.e., are self centralising. Can we prove that?

20. Aug 20, 2008

### the_fox

Oops.. sorry for the double post.