Let $A\in M_n(\mathbb{Q})$ with $A^k=I_n$. If $j$ is a positive integer with $\gcd(j,k)=1$, show that $ \operatorname{tr}(A)= \operatorname{tr}(A^j)$. 
Let $A\in M_n(\mathbb{Q})$ with $A^k=I_n$. If $j$ is a positive
     integer with $\gcd(j,k)=1$, show that $ \operatorname{tr}(A)=
   \operatorname{tr}(A^j)$.

I don't know how to start to prove that. I tried to find the matrix $B$ similar with $A$, but I am stuck...
Thank you.
 A: Note that eigenvalues $\lambda_i, i=1,\ldots, n$ of $A$ are roots of the rational polynomial
$$
p(t) = \det(tI-A)=\prod_{i=1}^n (t-\lambda_i).
$$ Since $Ax=\lambda_i x$ implies $A^kx = x = \lambda_i^k x$, we have $\{\lambda_i\}\subset \mu_k =\{\zeta\in\mathbb{C}\;|\;\zeta^k=1\}$. Let $\omega$ be the $k$-th primitive root of unity. Since $(j,k)=1$, we can define $\sigma\in \text{Aut}(\mathbb{Q}(\mu_k)/\mathbb{Q})$ by letting
$$
\sigma(\omega)= \omega^j.
$$ Then, it holds
$$
p(t) = \sigma(p(t)) = \sigma\left[\prod_{i=1}^n (t-\lambda_i)\right]=\prod_{i=1}^n (t-\sigma(\lambda_i))=\prod_{i=1}^n (t-\lambda_i^j).
$$ Now, it follows
$$
\text{tr}(A) = \sum_{i=1}^n \lambda_i =  \sum_{i=1}^n \lambda_i^j = \text{tr}(A^j).
$$
A: We must use the fact that $A\in M_n(\mathbb{Q})$ because the  result is false over $M_n(\mathbb{C})$. Indeed, consider $A=diag(e^{2i\pi/3},i)$ where $k=12$; then $trace(A)\not= trace(A^5)$.
$\textbf{Proposition.}$ When $A\in M_n(\mathbb{Q})$ and $(j,k)=1$, $spectrum(A)=spectrum(A^j)$.
$\textbf{Proof}.$ 
We may assume that $order(A)=k$ ($k=\min\{l;A^l=I_2\}$) and that $j<k$. Clearly, $order(A^j)=l$. $A$ is diagonalizable over $\mathbb{C}$ and its minimal polynomial divides $x^k-1$.
Therefore, $\chi_A$, the characteristic polynomial of $A$, is a product of (irreducible) cyclotomic polynomials $\phi_a(x)=\Pi_{(u,a)=1}(x-e^{2i\pi u/a})\in\mathbb{Q}[x]$ where $a|k$. Since $(j,a)=1$, it is easy to see that $\phi_a(x)=\Pi_{(u,a)=1}(x-(e^{2i\pi u/a})^j)$ and we are done.  $\square$
