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.

One can prove that the $\Phi_n(x)$ are irreducible over $\Bbb Z$. Where $\Phi_n(x)=\prod _{(a,n)=1}\zeta_n^a$ (i.e the product of the primitive n-rooth of unity). I want to find a factorization of $\Phi_n$ in $\Bbb F_p$. I proved that all the irreducible factors of $\Phi_n$ over $\Bbb F_p$ are of the same degree, and the degree of all of them is $d$. Where $d$ is the order of $p \in \Bbb Z_n^*$. And since $ Degree (\Phi_n ) = \phi(n) $, then $\Phi_n$ is a product of $ \frac{\phi(n)}{d}$ irreducible factors of degree $d$. To find an explicit factorization , one way is to put a system of equations to find the coefficients of the irreducible factors, but I think that it's very complicated.

I want to know if there is one way to do this, maybe considering what I said but more. Maybe some relation in the irreducible factors, would reduce the system or something like that.

share|improve this question
    
An earlier question and answers to it don't promise much :-). There the extra idea was that one factor was known to be reciprocal of the other. Sometimes factors are palindromic (their own reciprocals). I don't know of very many tricks for finding the factors in the general case. Have you looked up any textbooks (such as Lidl & Niederreiter)? –  Jyrki Lahtonen Nov 7 '12 at 15:57
    
One factor is the product of all $d$ conjugates of $(x - \zeta_n)$. –  Hurkyl Nov 7 '12 at 16:56
add comment

1 Answer

up vote 2 down vote accepted

Those factorisations follow the factorisation of $\Phi_n$ on intermediate fields between $\mathbb Q$ and $\mathbb Q(\zeta_n)$.

For example, let $n=12$. There are $4$ cases :

If $p = 1 \pmod {12}$, then $\Phi_{12}$ splits in $\mathbb F_p$, so you have to find one primitive root of $1$, $\zeta_{12}$, then write $\Phi_{12}(X) = (X- \zeta_{12})(X- \zeta_{12}^5)(X- \zeta_{12}^7)(X- \zeta_{12}^{11})$

If $p = 5 \pmod {12}$, then it has the same factorisation as the one on $\mathbb Q(i)$, which is $(X^2-iX-1)(X^2+iX-1)$, so you only need to find one of the two square roots of $ -1$ in $\mathbb F_p$ to get the factorisation.

If $p = 7 \pmod {12}$, then it has the same factorisation as the one on $\mathbb Q(j)$, which is $(X^2-j)(X^2-j^2)$, so you only need to find one of the two primitive third roots of $1$ in $\mathbb F_p$ to get the factorisation.

If $p = 11 \pmod {12}$, then it has the same factorisation as the one on $\mathbb Q(\sqrt 3)$, which is $(X^2-\sqrt 3 X + 1)(X^2+ \sqrt 3 X + 1)$, so you only need to find one of the two square roots of $3$ in $\mathbb F_p$ to get the factorisation.

In any case, finding those factorisations mean that you have to solve some algebraic equations in $\mathbb F_p$ (they are not always simple roots for example if $n=7$ you may have to find $\cos(2\pi/7)$ which is a root of a degree $3$ equation while it's not a cube root), and in some cases, you have to find one primitive $n$th root of $1$ root in $\mathbb F_p$.

I don't think there's a big leap in difficulty in simply finding one primitive root $\zeta_n$ in $\mathbb F_{p^d}$ and then computing the irreducible factors which are all the $(X- \zeta_n^k)(X - \zeta_n^{kp}) (X - \zeta_n^{kp^2})\ldots (X - \zeta_n^{kp^{d-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.