Elements in $\text{GL}(n,q)$ with irreducible characteristic polynomial Let $x,y\in\text{GL}(n,q)$ be of the same order such that both the characteristic polynomials of $x,y$ are irreducible. Must $x,y$ always be conjugate in $\text{GL}(n,q)$? More restrictly, I am interested in the $2$-dimensional case. But the general answer would be more welcome.
 A: First of all, since the characteristic polynomials are irreducible, they coincide with the minimal polynomials.
Let us deal with $n = 2$. The answer is no in general, but yes in one particular small case.
When $q = 2$, there is only one possible polynomial, that is $x^{2} + x + 1$, then the answer is affirmative, and we are talking elements of order $3$.
Now in general, take an irreducible polynomial $f = x^2 + a x + b$ in $\operatorname{GF}(q)[x]$, then note that its reciprocal $b x^2 + a x + 1$ is also irreducible, so that $g = x^2 + a b^{-1} x + b^{-1}$ is irreducible, and the roots of $g$ are the inverses of the roots of $f$. 
If $f \ne g$, then you can take the companion matrices of $f$ and $g$
$$
x = \begin{bmatrix}0&1\\-b&-a\end{bmatrix},
\qquad
y = \begin{bmatrix}0&1\\-b^{-1}&-ab^{-1}\end{bmatrix},
$$ 
and these will be non-conjugate elements (the minimal polynomials are different) of the same order (eigenvalues of one matrix are the inverses of eigenvalues of the other).
Now $f \ne g$ if either $a \ne 0$ and $b \ne 1$, or $a = 0$ and $b^{2} \ne 1$.
If $q \ne 2$, such polynomials $f$ always exist, because the norm $N_{\operatorname{GF}(q^{2})/\operatorname{GF}(q)}$ is surjective. In fact, you can always take $b \ne \pm 1$, unless $q = 3$. In this case, just note that the polynomial $f = x^{2} - x - 1$ is irreducible in $\operatorname{GF}(3)[x]$ (and $g = x^2 + x - 1 \ne f$.)
PS OK, general $n$ now. I hope the following is correct, as I wrote it a bit hurriedly, and there might be a simpler version.
The discussion above indicates that we are aiming at finding an irreducible polynomial of degree $n$ over $\operatorname{GF}(q)$ which is not symmetric, or equivalently an element of $\operatorname{GF}(q^n)$ of degree $n$ over $\operatorname{GF}(q)$ which is not Galois conjugate to its inverse. Now if all elements of $\operatorname{GF}(q^n)$ of degree $n$ over $\operatorname{GF}(q)$ are Galois conjugate to their inverses (actually, it is enough for this to hold for one primitive element), this holds for all elements of  $\operatorname{GF}(q^n)$, in particular it holds in all subfields. 
Consider first the case $q > 2$. We have seen that in $\operatorname{GF}(q^{2})$ not all elements of degree $2$ are conjugate to their inverses. So we quickly reduce to showing that not all elements of degree $p$ are conjugate to their inverses in $\operatorname{GF}(q^p)$, where $p$ is an odd prime. But there are $(q^{p} - q)/p$ monic, irreducible polynomials of degree $p$ over $\operatorname{GF}(q)$ here, and only (note: serious misprint corrected) $q^{(p-1)/2}$ symmetric polynomials. (Addendum: @user60079 notes in the comments below the much simpler argument that a symmetric polynomial of odd degree $> 1$ has always a root $\pm 1$, and is thus reducible.)
In case $q = 2$, we have also to deal with the possibility that $n = 2^{k}$, with $k \ge 2$. But then it is enough to note that the polynomial $x^{4} + x + 1$ is irreducible in $\operatorname{GF}(2)[x]$, and non-symmetric.
A: Let $f(X)=X^n+a_{n-1}X^{n-1}+\ldots +a_0$ be the common characteristic polynomial.
Select a nonzero vector $v\in\mathbb F_q^n$.
Then $v, xv,\ldots , x^{n-1}v$ are linearly independent beacuse any linear dependance $\sum c_i\cdot x^iv=0$ would translate into a polynomial $\sum c_iX^i$ of degree $\le n-1$ that is a factor of $f$.
Hence $v, xv,\ldots , x^{n-1}v$ are a basis of $\mathbb F_q^n$.
On the other hand, we have $x^nv = -(a_{n-1}x^{n-1}v+\ldots + a_0)$. Hence the matrix of $x$ with respect to $v, xv,\ldots , x^{n-1}v$ as basis is
$$\begin{pmatrix}0&0&\cdots&0&-a_0\\1&0&\cdots& 0&-a_1\\0&1&\cdots&0&-a_2\\
\vdots&&\ddots&&\vdots\\0&0&\cdots &1&-a_{d-1}\end{pmatrix} $$
We can do the same with respect to $y$ and since chosing a basis is the same as conjugation, $x$ and $y$ are conjugate.

Note that nothing special about finite fields was used, i.e. the result holds in $GL(n,F)$ for any $n$ and any field $F$.
