Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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
add comment

1 Answer

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$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.