# Minimal polynomials of "simple" algebraic numbers

This should be a fairly trivial question, to which I have nevertheless found no satisfactory answer.

I am interested in effective algorithmic computation of minimal polynomials of some particularly simple algebraic numbers, especially the complex $$n$$-th roots of rational numbers: $$\alpha = \sqrt[n]{q}e^{i2k\pi/n}.$$ Each such $$\alpha$$ is a root of the polynomial $$x^n - q$$, but the trouble is that this polynomial might not be irreducible over $$\mathbb{Q}$$. I know that the irreducible factors can be found in polynomial time, e.g., using the LLL algorithm. But how to determine the correct factor? This can usually be done easily by hand, but what about algorithmic computation? The only way of evaluating a polynomial at $$\alpha$$ that I am aware of already assumes that the minimal polynomial of $$\alpha$$ is known. Or should I use a completely different approach?

Moreover, since $$q$$ can be assumed to be an integer, an algorithm for computing minimal polynomials of algebraic integers would be sufficient. This MathOverflow answer suggest that computing minimal polynomials of algebraic integers is easy, but I was unable to find out why. Any reference would be helpful here.

• See this post. $x^n-q$ is irreducible, except for the case where $q=p^m$ for some prime $p$ dividing $n$. Aug 15, 2021 at 8:08
• With the aid of the minimal polynomial of $|q|^{1/n}$ and the roots of unity you get a field where you can work. Galois theory then tells us how to find the conjugates of $\alpha$. There are subtleties when $q$ is negative (see the second exceptional case). Aug 15, 2021 at 10:10