10
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ One factor is the product of all $d$ conjugates of $(x - \zeta_n)$. $\endgroup$ – user14972 Nov 7 '12 at 16:56
5
$\begingroup$

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}})$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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