# minimal polynomial of power of algebraic number

Consider any algebraic number $\alpha$ which is given by its minimal polynomial $f$. How can I compute the minimal polynomial of $\alpha^m$ for some natural number $m$? How efficient the algorithm is?

I assume that this problem is well-studied, but can anyone give me a reference, or some short description of the algorithm?

Thanks a lot!

• I think the minimal polynomial of $\alpha$ and the minimal polynomial of $\alpha^m$ are not strongly related. (Except of course in some special cases.) – rschwieb Oct 19 '12 at 12:09
• thanks. Somehow this question can be formulated as given $\alpha$, how to compute (symbolically) $\alpha^m$. I guess there must be some algorithm to do so. – user29271 Oct 19 '12 at 12:23

Here's one way --- I don't know how efficient it is.

You know the polynomial for $\alpha$. Say it has degree $d$. That means you can express any power of $\alpha$ as a rational linear combination of $1,\alpha,\dots,\alpha^{d-1}$. In particular, you can express any power of $\alpha^m$ as such a linear combination. Then you can test, for various $r$, whether $1,\alpha^m,\alpha^{2m},\dots,\alpha^{rm}$ is a linearly independent set over the rationals. As soon as you get a set that isn't, you have your minimal polynomial for $\alpha^m$.

EDIT: For example, suppose $\alpha$ is a zero of $x^3-x-1$, and find a polynomial for $\beta=\alpha^2$. Well, $\alpha^3=\alpha+1$; $\alpha^4=\alpha^2+\alpha$; $\alpha^5=\alpha^3+\alpha^2=\alpha^2+\alpha+1$; $\alpha^6=\alpha^3+\alpha^2+\alpha=\alpha^2+2\alpha+1$. We find that $1,\beta,\beta^2,\beta^3$ are linearly dependent: $2\beta^2-\beta^3=\beta-1$. So our polynomial is $x^3-2x^2+x-1$.

(This is a question I wanted to ask; and doing a search before asking led me to this post. This should explain why a 5-year old question is getting an answer now).

I have one way and I am not sure it is efficient. I think there is no loss of generality assuming $\alpha$ to be an algebraic integer. Take the matrix $A$ for which $f(x)$ is the companion matrix.

Now computer the matrix power $A^m$. Then factors of characteristic polynomial of $A^m$ will lead to minimal polynomial of $\alpha^m$.

(I am curious when the characteristic polynomial of $A^m$ would itself be irreducible.)

• The characteristic might not be irreducible. Simply consider x = sqrt(2). Now, the characteristic polynomial has degree 2, but the solution is x^2 = 2, needing only degree 1. – WorldSEnder Nov 4 at 4:45