# How to find a cyclotomic polynomial of degree d that decompose into d irreducible polynomials in $Z_6$?

More specifically, I need the degree $$d$$ to be around 1024. I can easily find the cyclotomic polynomial of degree 1024 that satisfies the above requirement in $$Z_2$$, i.e., $$x^{1024}+1$$, which is equal to $$(x+1)^{1024} \bmod 2$$. But I don't know either this type of cyclotomic polynomial exists or not in $$Z_6$$, nor do I know how to find it if it exists?

If this type of cyclotomic poly doesn't exist in $$Z_6$$, can I find a degree-$$d$$ cyclotomic polynomial that decomposes into $$d$$ irreducible polynomials in $$Z_{p \times q}$$ if $$p$$ and $$q$$ are two as small as possible primes? Or two as small as possible co-prime composites for that matter.

Thank you so much in advance.

• Am I right --- you do not care of the fact that $\mathbb Z_6$ is not factorial? May 15, 2019 at 6:23
• Sorry, I don't know that much about the theory of cyclotomic poly. Just happen to use it in a project. Would you please let me know why this matters? Does it imply this type of cyclotomic poly doesn't exist in $\mathbb{Z}_6$? Thanks. May 15, 2019 at 6:42
• Can I find a $d$-degree cyclotomic poly that decomposes into $d$ irreducible polys in $\mathbb{Z}_{p \times q}$ if $p$ and $q$ are two as small as possible primes? Or two as small as possible co-prime composites for that matter. May 15, 2019 at 6:59

Sorry, you are out of luck. Let $$\phi_n$$ denote the $$n$$-th cyclotomic polynomial. I will show that

(1) $$\phi_n$$ factors completely into linear factors modulo $$p$$ (a prime) if and only if $$n$$ is of the form $$m p^k$$ where $$m$$ divides $$p-1$$ and

(2) If $$\phi_n$$ factors completely into linear factors modulo $$pq$$ ($$p$$ and $$q$$ distinct primes) then $$n$$ divides $$\max(p-1,q-1)$$.

In particular, there are only finitely many such $$n$$ in case (2). If $$p$$ and $$q$$ are co-prime composites, then they are divisible by some pair $$p'$$ and $$q'$$ of distinct primes, so there are still only finitely many solutions.

Proof of (1): Let $$n = m p^k$$ with $$p$$ not dividing $$m$$. Then $$\phi_n(x) = \phi_m(x^{p^k})/\phi_m(x^{p^{k-1}})$$ so $$\phi_n(x) \equiv \phi_m(x)^{(p-1) p^{k-1}} \bmod p$$. Thus $$\phi_n$$ splits into linear factors if and only if $$\phi_m$$ does and we can restrict ourself to the case where $$m$$ is not divisible by $$p$$.

We know that $$x^{p-1}-1 \equiv \prod_{j=1}^{p-1} (x-j) \bmod p$$, so if $$m|p-1$$ then $$\phi_m(x)$$ is a products of linears modulo $$p$$.

In the reverse direction, suppose that $$m$$ does not divide $$p-1$$. Let $$d = GCD(m,p-1)$$, so $$d. We know that $$x^m-1$$ is squarefree modulo $$p$$ (since $$p$$ does not divide $$m$$), so we have $$GCD(x^d-1, \phi_m(x))=1$$ in $$\mathbb{F}_p[x]$$.

Now, suppose for the sake of contradiction that $$\phi_m(x) \mod p$$ had a linear factor, say $$x-a$$, and note that $$a \neq 0$$. Then $$a^m \equiv 1 \bmod p$$. We also know that $$a^{p-1} \equiv 1 \bmod p$$, so $$a^d-1 \equiv 1 \bmod p$$ and $$x-a$$ divides $$x^d-1$$. But we noted above that $$GCD(x^d-1, \phi_m(x))=1$$ in $$\mathbb{F}_p[x]$$, a contradiction. $$\square$$.

Proof of (2) If $$\phi_n$$ factors into linears modulo $$pq$$ then does so modulo $$p$$ and modulo $$q$$. So we want $$n = m p^k$$ with $$m|(p-1)$$ and $$n = m' q^{k'}$$ with $$m'|q-1$$. Without loss of generality, let $$p. If $$k'>0$$ then $$q|n$$ so $$q|m$$, but then $$m$$ cannot divide $$q-1$$. So, in fact, $$k'=0$$ and $$n=m'$$ divides $$q-1$$, as claimed. $$\square$$

We can make a more precise statement than (2): Taking $$p, we need $$n$$ to divide $$q-1$$ and to be of the form $$p^k m$$ with $$m$$ dividing $$p-1$$. This factorization will not be unique, for example, $$\phi_4(x) = (x+8)(x-8) = (x+18)(x-18) \bmod 65$$. (Note that $$4$$ divides $$5-1$$ and $$13-1$$.)