# Do two primitive $n$-th roots of unity over $\mathbb{F}_p$ induce a nice correspondence between the irreducible factors of $x^n-1$?

Let $\alpha,\beta$ be primitive $n$-th roots of unity in an extension of $\mathbb{F}_p$ ($p$ prime).

Let $S$ be the set of irreducible factors (over $\mathbb{F}_p$) of $x^n-1$.

Is there a function $F:S\rightarrow S$ satisfying the following condition?

For every integer $i$, if $p(x)\in S$ is the minimal polynomial of $\alpha^i$ over $\mathbb{F}_p$, then $F(p(x))$ is the minimal polynomial of $\beta^i$ over $\mathbb{F}_p$.

If such function $F$ exists, how is it defined?

If $\alpha$ and $\beta$ have the same minimal polynomial, then taking $F$ to be the identity on $S$ works. I feel we should be able to find a function $F$ satisfying the above condition even when $\alpha$ and $\beta$ have different minimal polynomials.

• If $\alpha$ and $\beta$ are primitive $n$th roots of unity, then don't they have the same minimal polynomial? Aug 22, 2013 at 12:40
• @GerryMyerson: I think they don't. The $n$-th cyclotomic polynomail $Q_n(x)$ is the product of $\Phi(n)/d$ irreducible polynomials, each of degree $d$, where $d$ is the multiplicative order of $p$ modulo $n$. These factors are different, I'll write up an example.
– Gils
Aug 22, 2013 at 12:44
• @GerryMyerson: Found this example on the net: Take $p=11$ and $n=12$. Then $Q_n(x)=(x^2+5x+1)(x^2-5x+1)$. Every root of each of these irreducible factors is a $12$-th root of unity.
– Gils
Aug 22, 2013 at 12:46
• Yes, sorry. Or $p=7$, $n=3$, $(x-2)(x-4)$. Aug 22, 2013 at 12:47
• If $\alpha$ is a chosen primitive $n$th root of unity (in some extension field of $\mathbb{F}_p$, then $\alpha^i$ and $\alpha^j$ share the same minimal polynomial, iff $i$ and $j$ belong to the same cyclotomic coset modulo $n$, i.e. $ip^k\equiv j\pmod n$ for some non-negative integer $k$. Aug 22, 2013 at 17:19

The following solves the problem of finding the minimal polynomial of $\alpha^i$ given the minimal polynomial of $\alpha$. If you know the exponent $e$ in $\beta=\alpha^e$, then you can apply this to your question. This has much higher complexity than taking the reciprocal as I indicated in a comment under the OP.

Assume that we know the minimal polynomial $m(x)$ os a primitive $n$th root $\alpha$, and that we want to calculate the minimal polynomial of another primitive root $\beta=\alpha^i$, $\gcd(i,n)=1$. First we find the modular inverse $j$ of $i$, so this is an integer with the property $ji\equiv1\pmod n.$ We then know that $\beta^j=\alpha$. Thus we know that $\beta$ is a zero of the polynomial $m(x^j)$. As $\beta$ is also a zero of $x^n-1$ we know that $\beta$ is a zero of $$m_j(x):=\gcd(x^n-1,m(x^j)).$$ I claim that $m_j(x)$ is the minimal polynomial of $\beta$. Let $\gamma$ be any zero of $m_j(x)$. As $m_j(x)\mid x^n-1$, we know that $\gamma$ has to be an $n$th root of unity, so $\gamma=\alpha^t$ for some integer $t$. As $\gamma^j$ is a zero of $m(x)$, we know that $\gamma^j$ is a conjugate of $\alpha$, i.e. $\gamma^j=\alpha^{p^k}$ for some non-negative integer $k$. But this means that $$\gamma=\gamma^{ij}=\alpha^{ip^k}=\beta^{p^k}$$ is a conjugate of $\beta$. Thus all the zeros of $m_j(x)$ are conjugates of $\beta$ proving the claim.

As an example let's take the irreducible factor $m(x)=x^2+5x+1$ of $x^{12}-1$ in the ring $\mathbb{Z}_{11}[x]$ given by Gils in a comment. We could check that the roots of $m(x)$ are, indeed, primitive twelfth roots of unity, but I'll skip that. We observe right away that $m(x)$ is palindromic, i.e. equal to its own reciprocal polynomial. This was to expected. For if $\alpha$ is a zero of $m(x)$, then the other zero is the Frobenius conjugate $\alpha^{11}=\alpha^{11-12}=\alpha^{-1}$. But we can use $j=5$ here as $\gcd(5,12)=1$. The above piece of theory tells us to calculate (Mathematica did this for me) $$m_5(x):=\gcd(m(x^5),x^{12}-1)=\gcd(x^{10}+5x^5+1,x^{12}-1)=x^2+6x+1=x^2-5x+1.$$ This is the other factor given by Gils. Its roots are $\alpha^5$ and $\alpha^{-5}=\alpha^7$. As an auxiliary check we observe that this time we knew that $\alpha^6=-1$ as that is the sole primitive second root of unity. Therefore $\alpha^7=\alpha\alpha^6=-\alpha$. Indeed, we immediately see that $m_5(x)=m(-x)$. This gives us another proof for the fact that $\alpha^7=-\alpha$ is a zero of $m_5(x)$

This method may not always be very low complexity, because the polynomial $m(x^j)$ may have a rather high degree, and calculating the gcd thus takes a while (with the pen & paper method). Some help can be gotten by replacing $x^n-1$ with the characteristic zero $n$th cyclotomic polynomial $\phi_n(x)$ of degree $\phi(n)<n$.

• May be not quite what you asked. Hopefully still helps. Aug 22, 2013 at 18:13
• So, if I understand correctly, for the mere question of existence of such function $F$, the answer is: Yes. Such function exists because for primitive $n$-th roots of unity $\alpha,\beta$ and integers $i,j$, we know that if $\alpha^i$ and $\alpha^j$ have the same minimal polynomial, then $i\equiv jp^k\pmod{n}$ for some integer $k$, and therefore $\beta^i$ and $\beta^j$ have the same minimal polynomial. Is that right?
– Gils
Aug 22, 2013 at 20:01
• And that also shows that the function $F$ sends a polynomial of degree $d$ to a polynomial of degree $d$, because the function $\alpha^i\mapsto\beta^i$ is a bijection of the $n$-th roots of unity, matching between sets of Galois conjugates in both directions. Is that right?
– Gils
Aug 22, 2013 at 20:06
• Correct, Gils. I'm a bit worried about not actually answering your question as stated. This is a method for finding the minimal polynomial of $\alpha^i$ given the minimal polynomial of $\alpha$. So to apply this to the question you asked, we need to first write $\beta$ as a power of $\alpha$. If $n$ is large, that is a very tall order (known as the discrete logarithm problem). Aug 22, 2013 at 20:08
• Thank you very much. The two observations in my comments are the most important to me, so your answer does satisfy me. As for efficient computation of $F$ - this is interesting, but less important to me. Will think about it too.
– Gils
Aug 22, 2013 at 20:13

If you choose a prime $\pi$ lying over $p$ in $\mathbb Z[\zeta_n]$, where $\zeta_n$ is a primitive $n$th root of $1$ in $\overline{\mathbb Q}$, it is possible to choose liftings to char=$0$ of those minimal polynomials so that the Galois group upstairs permutes them as desired, since the Galois group is transitive upstairs, and the lifts to char=$0$ can be chosen to correspond to intermediate fields upstairs, even if mod $p$ they give trivial maps on the fields themselves. I think. :)