# The factorization of $X^{n}-a$ and $f(X^{n})$ over $\mathbb{F}_{q}$

Anna-Maurin Graner
University of Rostock  Germany
<EMAIL_ADDRESS>
###### Abstract

The polynomial $X^{n}-1$ and its factorization over $\mathbb{F}_{q}$ have been
studied for a long time. Many results on this, and the closely related problem
of the factorization of the cyclotomic polynomials, exist. We study the
factorization of the polynomial $X^{n}-a$ with $a\in\mathbb{F}_{q}^{\ast}$.
This factorization has been studied for the case that there exist at most
three distinct prime factors of $n$. If there exists an element
$b\in\mathbb{F}_{q}$ such that $b^{n}=a$, the factorization of
$X^{n}-a=b^{n}\cdot((\frac{X}{b})^{n}-1)$ can easily be derived from the
factorization of $X^{n}-1$. We present the factorization of $X^{n}-a$ for any
positive integer $n$. Then we use our results to factor the composition
$f(X^{n})$, where $f$ is an irreducible polynomial over $\mathbb{F}_{q}$. The
factorization of $f(X^{n})$ is known for the case
$\gcd(n,\mathrm{ord}(f)\cdot\deg(f))=1$. Our results allow us to give the
factorization of $f(X^{n})$ for any positive integer $n$.

Keywords: Factorization, irreducible polynomials, composition.

##  1 Introduction

Let $\mathbb{F}_{q}$ be a finite field of $q$ elements and of characteristic
$\text{char}(\mathbb{F}_{q})$. Let $n$ be a positive integer and
$n=p_{1}^{i_{1}}\cdots p_{m}^{i_{m}}$ its decomposition into powers of
distinct primes $p_{1},\ldots,p_{m}$. Then $\nu_{p_{j}}(n)=i_{j}$ denotes the
$p_{j}$-adic value of $n$ and we call $\operatorname{rad}(n):=p_{1}\ldots
p_{m}$ the radical of $n$. If $\gcd(n,q)=1$, then there exists a primitive
$n$-th root of unity in the splitting field $\overline{\mathbb{F}}_{q}$, which
we denote by $\zeta_{n}$. For a positive integer $m$ such that $\gcd(n,m)=1$
the multiplicative order of $m$ in $\mathbb{Z}/n\mathbb{Z}$ is
$\operatorname{ord}_{n}(m)$. Thus, $\zeta_{n}$ is an element of the extension
field $\mathbb{F}_{q^{\operatorname{ord}_{n}(q)}}$.

Throughout this paper let $f\in\mathbb{F}_{q}[X]$ be an irreducible polynomial
of degree $k$. Further, let $\alpha$ be a root of $f$ and
$\operatorname{ord}(\alpha)=\operatorname{ord}(f)$ be its order in the
multiplicative group $\mathbb{F}_{q^{k}}^{\ast}$.

For many applications in cryptography and coding theory the factorization of
polynomials over a finite field $\mathbb{F}_{q}$ is needed. In particular, the
factorization of the polynomial $X^{n}-a$ for $a\in\mathbb{F}_{q}^{\ast}$ is
used for the construction of $a$-constacyclic codes of length $n$ (see
[Che+12, Liu+17, LY18, SF20, Rak+22]). If $a=1$, then $X^{n}-1$ yields a
cyclic code. Cyclic codes have been well studied and their construction is
closely related to the factorization of the cyclotomic polynomials. The second
polynomial which we study in this paper is the composition $f(X^{n})$.
Compositions of a polynomial with a rational function are widely used for the
construction of irreducible polynomials. The classical composition method
searches for a rational function $Q=\frac{g}{h}\in\mathbb{F}_{q}$ such that
the composition $f^{Q}:=h^{k}\cdot f(\frac{g}{h})$ is irreducible. Variations
of this method search for irreducible factors of the composition $f^{Q}$ (see
[Ugo16]).

The composition that we study in this paper is $f(X^{n})$. Its explicit
factorization is known for the case $\gcd(n,\operatorname{ord}(\alpha)\cdot
k)=1$ (see [BRS19]). The next theorems show that the factorization of
$f(X^{n})$ can be obtained from the factorization of the polynomial
$X^{n}-\alpha$ over $\mathbb{F}_{q^{k}}$. Therefore it is not necessary to
study the factorization of $f(X^{n})$ itself. This is due to the fact that the
composition $f(X^{n})$ is a rational transformation of the form $f^{Q}$ where
$Q=\frac{X^{n}}{1}$. The polynomial $f^{Q}$ is directly connected to the
polynomial $g-\alpha h$ over $\mathbb{F}_{q^{k}}$, as we can see from the
following well-known theorem by Cohen.

######  Theorem 1 ([Coh69, Lemma 1]).

Let $f\in\mathbb{F}_{q}[X]$ be an irreducible polynomial of degree $k$ and
$\alpha\in\mathbb{F}_{q^{k}}$ be a root of $f$. Further, let
$Q=\frac{g}{h}\in\mathbb{F}_{q}[X]$ be a rational function over
$\mathbb{F}_{q}$. Then the polynomial $f^{Q}$ is irreducible over
$\mathbb{F}_{q}$ if and only if the polynomial $g-\alpha h$ is irreducible
over $\mathbb{F}_{q^{k}}$.

Kyuregyan and Kyureghyan gave a proof in [KK11] for Theorem 1 which can be
tweaked to show that the factorization of $g-\alpha h$ yields the
factorization of $f^{Q}$. This fact is stated in Theorem 3, which was
presented in [MYM10]. Since the paper is not publicly available, we present
the proof of Theorem 3 here. For its formulation and its proof we need the
following definitions and Theorem 2.

For positive integers $j$ and $d$, and a polynomial
$h(X)=\sum_{i=0}^{m}a_{i}X^{i}$ over $\mathbb{F}_{q^{d}}$, we define the
polynomial

${h}^{(j)}(X):=\sum_{i=0}^{m}a_{i}^{q^{j}}X^{i}.$

Note that $h^{(j)}=h$ if $j$ is a multiple of
$[\mathbb{F}_{q}(a_{0},\ldots,a_{m}):\mathbb{F}_{q}]$, the extension degree of
$\mathbb{F}_{q}(a_{0},\ldots,a_{m})$ over $\mathbb{F}_{q}$. The extension
degree $[\mathbb{F}_{q}(a_{0},\ldots,a_{m}):\mathbb{F}_{q}]$ plays a key role
in the arguments to come. We denote it by
$\mathrm{coeffdeg}_{q}\left(h\right)$ and call it the degree of the
coefficients of $h$ over $\mathbb{F}_{q}$.

######  Theorem 2 ([KK11, Lemma 1]).

Let $g\in\mathbb{F}_{q}[X]$ be a monic polynomial of degree $dm$, where
$d,m\in\mathbb{N}$. Then $g$ is irreducible over $\mathbb{F}_{q}$ if and only
if there exists a monic irreducible polynomial $h$ of degree $m$ over
$\mathbb{F}_{q^{d}}$ such that $\mathrm{coeffdeg}_{q}\left(h\right)=d$ and

$g=\prod_{j=0}^{d-1}{h}^{(j)}.$

From Theorem 2 follows directly, that for a monic irreducible polynomial $h$
of degree $m$ over $\mathbb{F}_{q^{d}}$ such that
$\mathrm{coeffdeg}_{q}\left(h\right)=d$ the polynomial
$\prod_{j=0}^{d-1}h^{(j)}$ is a monic irreducible polynomial of degree $dm$
over $\mathbb{F}_{q}$. We call this polynomial the $q$-spin of $h$ and denote
it by $\mathrm{spin}_{q}\left[h\right]$. Note that if
$\beta\in\mathbb{F}_{q^{dm}}$ is a root of $h$, then $h$ is the minimal
polynomial of $\beta$ over $\mathbb{F}_{q^{d}}$ and $g$ is the minimal
polynomial of $\beta$ over $\mathbb{F}_{q}$. With the definition of the
$q$-spin we can formulate Theorem 3.

######  Theorem 3 ([MYM10, Lemma 13]).

Let $f\in\mathbb{F}_{q}[X]$ be an irreducible polynomial of degree $k$ and
$\alpha\in\mathbb{F}_{q^{k}}$ be a root of $f$. Further, let
$Q=\frac{g}{h}\in\mathbb{F}_{q}[X]$ and $\prod_{R}R$ be the factorization of
$g-\alpha h$ into irreducible factors over $\mathbb{F}_{q^{k}}$. Then the
factorization of $f^{Q}$ into irreducible factors over $\mathbb{F}_{q}$ is
given by

$\prod_{R}\mathrm{spin}_{q}\left[R\right],$

where $\mathrm{coeffdeg}_{q}\left(R\right)=k$ for all irreducible factors $R$
of $g-\alpha h$ over $\mathbb{F}_{q^{k}}$.

###### Proof of Theorem 3.

Since $f$ is an irreducible polynomial of degree $k$ and $\alpha$ is a root of
$f$, the decomposition of $f$ over $\mathbb{F}_{q^{k}}$ is
$f(X)=\prod_{j=0}^{k-1}(X-\alpha^{q^{j}})$. Thus, the $Q$-transform of $f$
considered over $\mathbb{F}_{q^{k}}$ satisfies:

$f^{Q}=h^{k}\cdot
f\left(\frac{g}{h}\right)=\prod_{j=0}^{k-1}(g-\alpha^{q^{j}}\cdot
h)=\prod_{j=0}^{k-1}{(g-\alpha
h)}^{(j)}=\prod_{j=0}^{k-1}{\left(\prod_{R}R\right)}^{(j)}=\prod_{j=0}^{k-1}\prod_{R}{R}^{(j)},$

because $g,h\in\mathbb{F}_{q}[X]$ and therefore ${g}^{(j)}=g$ and
${h}^{(j)}=h$ for all $0\leq j\leq{k-1}$. Furthermore, if $\prod_{R}R$ is the
factorization of $g-\alpha h$ over $\mathbb{F}_{q^{k}}$, then for every
irreducible factor $R$ the degree of its coefficients over $\mathbb{F}_{q}$
must be equal to $k$. Indeed, if $\mathrm{coeffdeg}_{q}\left(R\right)=m<k$ and
$\gamma\in\mathbb{F}_{q^{m}}$ were a root of $R$, then $\gamma$ would be a
root of $g-\alpha h$ satisfying $g(\gamma)-\alpha\cdot h(\gamma)=0$. However
$g(\gamma)$ and $h(\gamma)$ are elements of $\mathbb{F}_{q^{m}}$, which
implies that $\alpha\cdot h(\gamma)$ cannot be equal to $g(\gamma)$, a
contradiction. Consequently, the $q$-spin of $R$ is equal to
$\mathrm{spin}_{q}\left[R\right]=\prod_{j=0}^{k-1}{R}^{(j)}$ and

$f^{Q}=\prod_{R}\left(\prod_{j=0}^{k-1}{R}^{(j)}\right)=\prod_{R}\mathrm{spin}_{q}\left[R\right].$

∎

From Theorem 3 follows directly that it suffices to study the factorization of
$g-\alpha h$ over $\mathbb{F}_{q^{k}}$ to obtain the factorization of $f^{Q}$.
For the rational function $Q=\frac{X^{n}}{1}$, this is the polynomial
$X^{n}-\alpha$. Many results on the factorization of $X^{n}-1$ exist (see
[BGM93, LN94, Mey96, Ste01, FY07, WW12, TW13, BGO15, Wu+17, Als18, WYF18,
OR21]). Even though the case $\alpha=1$ only applies if $f=X-1$, these results
can yield the factorization of $f(X^{n})$ for polynomials $f$ such that there
exists an element $\beta$ in $\mathbb{F}_{q^{k}}$ with $\beta^{n}=\alpha$. The
reason for this is that in this case the factorization of $X^{n}-\alpha$ can
easily be obtained from the factorization of $X^{n}-1$. In terms of
constacyclic codes, the $\alpha$-constacyclic code is isometric to a cyclic
code (see [Che+12, Corollary 3.4]). We reformulate this property in the two
following results and provide a proof using the concepts introduced above.

######  Proposition 4.

Let $n\in\mathbb{N}$ and $f\in\mathbb{F}_{q}[X]$ be an irreducible polynomial
of degree $k$. Further, let $\alpha\in\mathbb{F}_{q^{k}}$ be a root of $f$
such that there exists $\beta\in\mathbb{F}_{q^{k}}$ with $\beta^{n}=\alpha$.
If $\prod_{R}R$ is the factorization of $X^{n}-1$ into monic irreducible
factors over $\mathbb{F}_{q^{k}}$, then the factorization of $X^{n}-\alpha$
into monic irreducible factors over $\mathbb{F}_{q^{k}}$ is $\prod_{R}R^{Q}$,
where $Q=\frac{X}{\beta}\in\mathbb{F}_{q^{k}}[X]$.

###### Proof.

Since $\beta^{n}=\alpha$, we can write

$X^{n}-\alpha=X^{n}-\beta^{n}=\beta^{n}\left(\left(\frac{X}{\beta}\right)^{n}-1\right)=\beta^{n}\prod_{R}R\left(\frac{X}{\beta}\right)=\prod_{R}\beta^{\deg(R)}R\left(\frac{X}{\beta}\right)=\prod_{R}R^{Q}.$

For every monic irreducible factor $R$ let $\gamma_{R}$ be a root of $R$. Then
the polynomial $X-\gamma_{R}\cdot\beta$ is irreducible over
$\mathbb{F}_{q^{k\cdot\deg(R)}}$. Thus, with Theorem 1 the polynomial $R^{Q}$
is irreducible over $\mathbb{F}_{q^{k}}$, which concludes our proof. ∎

The following theorem is the combination of Proposition 4 and Theorem 3.

######  Proposition 5.

Let $n\in\mathbb{N}$ and $f\in\mathbb{F}_{q}[X]$ be an irreducible polynomial
of degree $k$. Further, let $\alpha\in\mathbb{F}_{q^{k}}$ be a root of $f$
such that there exists $\beta\in\mathbb{F}_{q^{k}}$ with $\beta^{n}=\alpha$.
If $\prod_{R}R$ is the factorization of $X^{n}-1$ into monic irreducible
factors over $\mathbb{F}_{q^{k}}$. Then the factorization of $f(X^{n})$ into
monic irreducible factors over $\mathbb{F}_{q}$ is

$\prod_{R}\mathrm{spin}_{q}\left[R^{Q}\right],$

where $Q=\frac{X}{\beta}\in\mathbb{F}_{q^{k}}[X]$.

It is well known that there exists an element $\beta\in\mathbb{F}_{q^{k}}$
such that $\beta^{n}=\alpha$ if and only if
$\alpha^{\frac{q^{k}-1}{\gcd(n,q^{k}-1)}}=1$. If the order of $\alpha$ is
large and $n$ is not coprime with $q^{k}-1$, it is likely that such an element
$\beta$ does not exist. Therefore, we need to find the factorization of
$X^{n}-\alpha$ over $\mathbb{F}_{q^{k}}$ for $\alpha\neq 1$ in general. For
this, we study the factorization of $X^{n}-a\in\mathbb{F}_{q}[X]$, where
$a\in\mathbb{F}_{q}^{\ast}$, in Section 2 and present the resulting
factorization of $f(X^{n})$ in Section 3.

The results on the factorization of $X^{n}-1$ and $f(X^{n})$ given in [BGO15,
WYF18, WY21, BRS19] are proved with a top-down approach. By this, we mean that
for a polynomial $g$ over $\mathbb{F}_{q}$, the authors first name the
irreducible factors over $\mathbb{F}_{q}$. Then, they show that the named
polynomials are irreducible over $\mathbb{F}_{q}$ and factors of $g$. In the
last step, the argument that the sum of the degrees of the named polynomials
equals the degree of $g$ concludes their proof.

We use a bottom-up approach and prove our results in Section 2 via induction.
More precisely, if $n=p_{1}\cdots p_{m}$ is the factorization of $n$ into
prime factors, we decompose

$X^{p_{1}}-\alpha,\;\left(X^{p_{2}}\right)^{p_{1}}-\alpha,\;\left(\left(X^{p_{3}}\right)^{p_{2}}\right)^{p_{1}}-\alpha,\ldots,\left(\ldots\left(X^{p_{m}}\right)^{p_{m-1}}\ldots\right)^{p_{1}}-\alpha$

inductively.

The advantage of this method is that the proof itself shows why the factors
are given as they are and it allows us to determine the exact order of the
appearing coefficients. This order is needed to decide on the irreducibility
of the factors. Our results are generalizations of the existing results on the
factorization of $X^{n}-1$. Therefore, we introduce an alternative proof for
them, which gives additional information on the order and other properties of
the coefficients that appear.

##  2 The factorization of $X^{n}-a$

Let $a\in\mathbb{F}_{q}^{\ast}$. The factorization of $X^{n}-a$ has been
studied in the context of $a$-constacyclic codes and is known for positive
integers $n$ such that $n=p_{1}^{m_{1}}\cdot p_{2}^{m_{2}}\cdot
p_{3}^{m_{3}}$, where $p_{1},p_{2},p_{3}$ are distinct primes (see [Rak+22]).
In this section we present the explicit factorization of $X^{n}-a$ over
$\mathbb{F}_{q}$ for any positive integer $n$.

Without loss of generality we can assume that $\gcd(n,q)=1$. Indeed, if
$\gcd(n,q)>1$, then $n=\tilde{n}\cdot\text{char}(\mathbb{F}_{q})^{l}$ for
positive integers $\tilde{n},l$. Then there exists an element
$b\in\mathbb{F}_{q}$ such that $b^{\text{char}(\mathbb{F}_{q})^{l}}=a$,
because $a^{\frac{q-1}{\gcd(\text{char}(\mathbb{F}_{q})^{l},q-1)}}=a^{q-1}=1$.
Thus, the polynomial $X^{n}-a$ equals
$(X^{\tilde{n}}-b)^{\text{char}(\mathbb{F}_{q})^{l}}$ and it suffices to
factor the polynomial $X^{\tilde{n}}-b$.

We prove our results by induction on the number of (not necessarily distinct)
prime factors of $n$. The base case is the factorization of $X^{p}-a$ for a
prime $p$ such that $\gcd(p,q)=1$. In the splitting field
$\overline{\mathbb{F}}_{q}$ there exists an element
$b\in\overline{\mathbb{F}}_{q}$ such that $b^{p}=a$. Then the polynomial
$X^{p}-a$ splits as $\prod_{j=0}^{p-1}(X-\zeta_{p}^{j}b)$, where $\zeta_{p}$
is a $p$-th primitive root of unity over $\mathbb{F}_{q}$. Using Theorem 2,
the factorization of $X^{p}-a$ depends on the degree of the coefficients of
$(X-\zeta_{p}^{j}b)$ over $\mathbb{F}_{q}$. Since
$\mathrm{coeffdeg}_{q}\left(X-\zeta_{p}^{j}b\right)=\operatorname{ord}_{\operatorname{ord}(\zeta_{p}^{j}b)}(q)$,
it is determined by the order of the roots $\zeta_{p}^{j}b$. The following
proposition specifies this order for the two cases
$p\mid\operatorname{ord}(\alpha)$ and $p\nmid\operatorname{ord}(\alpha)$.

######  Proposition 6.

Let $a\in\mathbb{F}_{q}^{\ast}$ and $p$ prime such that $\gcd(p,q)=1$. Then
the following statements hold:

  1. (i)

If $p\nmid\operatorname{ord}(a)$, then there exists $r\in\mathbb{N}$ such that
$rp\equiv 1\pmod{\operatorname{ord}(a)}$, $(a^{r})^{p}=a$ and
$\operatorname{ord}(a^{r})=\operatorname{ord}(a)$. Furthermore,
$\operatorname{ord}(\zeta_{p}^{j}a^{r})=p\cdot\operatorname{ord}(a)$ for all
$1\leq j\leq p-1$.

  2. (ii)

If $p\mid\operatorname{ord}(a)$, then every root
$b\in\overline{\mathbb{F}}_{q}$ of the polynomial $X^{p}-a$ has order
$\operatorname{ord}(b)=p\cdot\operatorname{ord}(a)$.

###### Proof.

Note that for any element $b\in\overline{\mathbb{F}}_{q}$ such that $b^{p}=a$,
the order of $b$ satisfies

$\operatorname{ord}(b)=\operatorname{ord}(a)\cdot\gcd(\operatorname{ord}(b),p)\in\\{\operatorname{ord}(a),\operatorname{ord}(a)\cdot
p\\}.$ (1)

  1. (i)

If $p\nmid\operatorname{ord}(a)$, then there exists $r\in\mathbb{N}$ such that
$rp\equiv 1\pmod{\operatorname{ord}(a)}$ and the element
$a^{r}\in\mathbb{F}_{q}$ satisfies $(a^{r})^{p}=a$. Since $a^{r}$ is an
element of the multiplicative group $\langle
a\rangle\leq\mathbb{F}_{q}^{\ast}$, its order divides $\operatorname{ord}(a)$.
This fact combined with eq. 1 yields that
$\operatorname{ord}(a^{r})=\operatorname{ord}(a)$. For every $1\leq j\leq
p-1$, the element $\zeta_{p}^{j}$ has order $p$, which is coprime with
$\operatorname{ord}(a)$. Therefore, we can conclude that
$\operatorname{ord}(\zeta_{p}^{j}a^{r})=p\cdot\operatorname{ord}(a)$ for
$1\leq j\leq p-1$.

  2. (ii)

If $p\mid\operatorname{ord}(a)$, then with eq. 1 also
$p\mid\operatorname{ord}(b)$. Suppose that
$\operatorname{ord}(b)=\operatorname{ord}(a)$. With the fact that $a=b^{p}$,
we know that
$\operatorname{ord}(a)=\frac{\operatorname{ord}(b)}{\gcd(\operatorname{ord}(b),p)}=\frac{\operatorname{ord}(b)}{p}=\frac{\operatorname{ord}(a)}{p}$,
a contradiction. Consequently, our assumption must have been false and we have
$\operatorname{ord}(b)=\operatorname{ord}(a)\cdot p$.

∎

Note that, with Proposition 6, for a prime $p$ such that $p\mid q-1$ and
$p\nmid\operatorname{ord}(a)$, the polynomial $X^{p}-a$ always decomposes in
$\mathbb{F}_{q}[X]$. Furthermore, in both cases, $p\nmid\operatorname{ord}(a)$
and $p\mid\operatorname{ord}(a)$, there exists a root of $X^{p}-a$ of order
$p\cdot\operatorname{ord}(a)$. We can easily derive the following corollary.

######  Corollary 7.

Let $a\in\mathbb{F}_{q}^{\ast}$ and $p$ prime such that $p\mid(q-1)$. Then
there exists $b\in\mathbb{F}_{q}$ such that $b^{p}=a$ if and only if
$p\cdot\operatorname{ord}(a)\mid(q-1)$.

###### Proof.

If $p\cdot\operatorname{ord}(a)\mid(q-1)$, then with Proposition 6 all roots
of $X^{p}-a$ are elements of $\mathbb{F}_{q}$. It remains to argue that if one
root $b$ of $X^{p}-a$ lies in $\mathbb{F}_{q}$, then all roots
$\zeta_{p}^{j}b$ for $0\leq j\leq p-1$ are elements of $\mathbb{F}_{q}$,
because $\zeta_{p}\in\mathbb{F}_{q}$. Thus, the order of every root of
$X^{p}-a$ divides $q-1$ and in particular the order
$p\cdot\operatorname{ord}(a)$. ∎

As the following theorem by Serret, Theorem 8, shows, the irreducibility of
the binomial $X^{t}-a$ for a positive integer $t$ depends mainly on the order
of $a$. Since Proposition 6 and Corollary 7 give the order of the roots of
$X^{p}-a$, they are the key elements for the theorems to come.

######  Theorem 8 ([LN94, Theorem 3.75]).

Let $t\geq 2$. Then the binomial $X^{t}-a$ is irreducible in
$\mathbb{F}_{q}[X]$ if and only if the following three conditions are
satisfied:

  1. (i)

$\operatorname{rad}(t)\mid\operatorname{ord}(a)$,

  2. (ii)

$\gcd(t,\frac{q-1}{\operatorname{ord}(a)})=1$,

  3. (iii)

$4\nmid t$ or $q\equiv 1\pmod{4}$.

###  2.1 The factorization of $X^{n}-a$
for the case $\operatorname{rad}(n)\mid q-1$, $4\nmid n$ or $q\equiv
1\pmod{4}$

In the next theorem we combine Corollary 7 and Theorem 8 to obtain a result
which can be applied recursively. More precisely, given an irreducible
polynomial $X^{t}-a$ over $\mathbb{F}_{q}$, we give an easy irreducibility
criterion for the polynomial $X^{tp}-a$. We begin with the case $4\nmid tp$ or
$q\equiv 1\pmod{4}$. The case $4\mid tp$ and $q\equiv 3\pmod{4}$ will be
discussed in the the next subsection.

######  Theorem 9.

Let $a\in\mathbb{F}_{q}^{\ast}$, $p$ be a prime such that $p\mid(q-1)$ and let
$t\in\mathbb{N}$ such that $X^{t}-a$ is irreducible over $\mathbb{F}_{q}$.
Further, let $4\nmid tp$ or $q\equiv 1\pmod{4}$. Then $X^{tp}-a$ is
irreducible over $\mathbb{F}_{q}$ if and only if
$p\cdot\operatorname{ord}(a)\nmid(q-1)$.

###### Proof.

We show that $X^{tp}-a$ is irreducible over $\mathbb{F}_{q}$ if and only if
there does not exist $b\in\mathbb{F}_{q}$ such that $b^{p}=a$. Then Corollary
7 completes the statement.

Suppose that there exists $b\in\mathbb{F}_{q}$ such that $b^{p}=a$. Then the
polynomial $X^{tp}-a$ in $\mathbb{F}_{q}[X]$ satisfies
$X^{tp}-a=\prod_{j=0}^{p-1}(X^{t}-\zeta_{p}^{j}b)$ and it is reducible.

Suppose that there does not exist $b\in\mathbb{F}_{q}$ such that $b^{p}=a$.
Then all roots of $X^{p}-a$ lie in true extension fields of $\mathbb{F}_{q}$.
Let $b\in\mathbb{F}_{q}(b)$ be a root of $X^{p}-a$. Then since
$\zeta_{p}\in\mathbb{F}_{q}$, we have $\zeta_{p}^{j}b\in\mathbb{F}_{q}(b)$ for
all $1\leq j\leq p-1$. Vice versa,
$b=\zeta_{p}^{-j}\cdot\zeta_{p}^{j}b\in\mathbb{F}_{q}(\zeta_{p}^{j}b)$. Thus,
the degree of the minimal polynomial of every root of $X^{p}-a$ is equal to
$[\mathbb{F}_{q}(b):\mathbb{F}_{q}]$. Since $X^{p}-a$ is a product of the
minimal polynomials of its roots over $\mathbb{F}_{q}$, there exists a
positive integer $m$ such that $p=m\cdot[\mathbb{F}_{q}(b):\mathbb{F}_{q}]$.
The two facts that $p$ is prime and $b$ is not an element of $\mathbb{F}_{q}$
imply that $[\mathbb{F}_{q}(b):\mathbb{F}_{q}]=p$ and $X^{p}-a$ is irreducible
over $\mathbb{F}_{q}$.

Theorem 8 yields that $p\mid\operatorname{ord}(a)$ and
$\gcd(p,\frac{q-1}{\operatorname{ord}(a)})=1$. Furthermore, since $X^{t}-a$ is
irreducible over $\mathbb{F}_{q}$, we have
$\operatorname{rad}(t)\mid\operatorname{ord}(a)$,
$\gcd(t,\frac{q-1}{\operatorname{ord}(a)})=1$. As a direct consequence we
obtain that $\operatorname{rad}(tp)\mid\operatorname{ord}(a)$ and also
$\gcd(tp,\frac{q-1}{\operatorname{ord}(a)})=1$. Since we assumed that $4\nmid
tp$ or $q\equiv 1\pmod{4}$, the third condition of Theorem 8 is satisfied and
we can conclude that $X^{tp}-a$ is irreducible over $\mathbb{F}_{q}$. ∎

The following corollary states the useful fact that for a prime $p$ such that
$p\mid t$ the polynomial $X^{tp}-a$ is irreducible if $X^{t}-a$ is irreducible
and ($4\nmid tp$ or $q\equiv 1\pmod{4}$).

######  Corollary 10.

Let $a\in\mathbb{F}_{q}^{\ast}$, $p$ be a prime such that $p\mid(q-1)$ and let
$t\in\mathbb{N}$ such that $X^{t}-a$ is irreducible over $\mathbb{F}_{q}$.
Further, let $4\nmid tp$ or $q\equiv 1\pmod{4}$. Then if $p$ divides $t$ the
polynomial $X^{tp}-a$ is irreducible over $\mathbb{F}_{q}$.

###### Proof.

Since $X^{t}-a$ is irreducible over $\mathbb{F}_{q}$, Theorem 8 implies that
$\gcd(t,\frac{q-1}{\operatorname{ord}(a)})=1$. If $p\mid t$, then also
$\gcd(p,\frac{q-1}{\operatorname{ord}(a)})=1$ and
$p\cdot\operatorname{ord}(a)$ cannot divide $(q-1)$. Theorem 9 completes our
proof. ∎

With Corollary 10 we do not need to compare the properties of $t$ and
$\operatorname{ord}(a)$ as specified in Theorem 8 (i) and (ii), if $p\mid t$.
This simplifies the check for irreducibility significantly.

Using Proposition 6 and Theorem 9, the following theorem gives the
factorization of $X^{tp}-a$ for the case that the polynomial is reducible over
$\mathbb{F}_{q}$ and ($4\nmid tp$ or $q\equiv 1\pmod{4}$).

######  Theorem 11.

Let $a\in\mathbb{F}_{q}^{\ast}$, $p$ be a prime such that $p\mid(q-1)$ and let
$t\in\mathbb{N}$ such that $X^{t}-a$ is irreducible over $\mathbb{F}_{q}$.
Further, let $4\nmid tp$ or $q\equiv 1\pmod{4}$. Then if
$p\cdot\operatorname{ord}(a)\mid(q-1)$, the factorization of $X^{tp}-a$ into
monic irreducible factors over $\mathbb{F}_{q}$ is

$X^{tp}-a=\prod_{j=0}^{p-1}(X^{t}-\zeta_{p}^{j}b),$

where $b\in\mathbb{F}_{q}$ such that $b^{p}=a$.

  1. (i)

If $p\nmid\operatorname{ord}(a)$, then $b=a^{r}$ for a positive integer $r$
satisfying $rp\equiv 1\pmod{\operatorname{ord}(a)}$ and
$\operatorname{ord}(b)=\operatorname{ord}(a)$.

  2. (ii)

If $p\mid\operatorname{ord}(a)$,
$\operatorname{ord}(b)=p\cdot\operatorname{ord}(a)$.

Furthermore, $\operatorname{ord}(\zeta_{p}^{j}b)=p\cdot\operatorname{ord}(a)$
for all $1\leq j\leq p-1$.

###### Proof.

The statement follows directly from Proposition 6 and Theorem 9. ∎

Theorems 9 and 11 can be applied recursively and we use them for the induction
step in the proofs of the next two theorems. Note that Theorems 9 and 11 allow
us to factor the polynomial $X^{tp}-a$ just by examining the order of the
element $a$ and comparing it with $p$ and $q-1$. This is why Theorem 11 (i)
and (ii), which specify the orders of the new appearing coefficients, are of
great importance. These statements allow us to decide on the irreduciblity in
the next induction step.

Theorems 12 and 13 specify the factorization of the polynomial $X^{tn}-a$ for
the two cases $\operatorname{rad}(n)\mid\operatorname{ord}(a)$ and
$\gcd(n,\operatorname{ord}(a))=1$, where $X^{t}-a$ is irreducible over
$\mathbb{F}_{q}$.

######  Theorem 12.

Let $a\in\mathbb{F}_{q}^{\ast}$, $t\in\mathbb{N}$ such that $X^{t}-a$ is
irreducible over $\mathbb{F}_{q}$ and let $n\in\mathbb{N}$ such that
$\operatorname{rad}(n)\mid\operatorname{ord}(a)$. Further, let $4\nmid tn$ or
$q\equiv 1\pmod{4}$. Set $d:=\gcd(n,\frac{q-1}{\operatorname{ord}(a)})$. Then
the factorization of $X^{tn}-a$ into monic irreducible factors over
$\mathbb{F}_{q}$ is

$\prod_{j=0}^{d-1}(X^{t\cdot\frac{n}{d}}-\zeta_{d}^{j}b),$

where $b\in\mathbb{F}_{q}$ such that $b^{d}=a$ and
$\operatorname{ord}(\zeta_{d}^{j}b)=\operatorname{ord}(a)\cdot d$ for all
$0\leq j\leq d-1$.

###### Proof.

We use the fact that every positive integer $n$ can be written as a product of
prime factors and prove the statement by induction on the number of prime
factors of $n$. Base case: If $n=p$ for a prime $p$ such that $p\mid q-1$ and
$p\mid\operatorname{ord}(a)$, the statement follows directly from Theorem 11
(i).

Induction hypothesis: Suppose that the statement of Theorem 13 holds for
$n,d,b$ such that
$\operatorname{rad}(n)\mid\operatorname{ord}(a),d=\gcd(n,\frac{q-1}{\operatorname{ord}(a)})$
and $b^{d}=a$.

Induction step $(n\rightarrow np)$: Let $p$ be a prime such that
$p\mid\operatorname{ord}(a)$, then

$X^{tnp}-a=\prod_{j=0}^{d-1}(X^{t\cdot\frac{n}{d}\cdot p}-\zeta_{d}^{j}b).$
(2)

If $dp$ does not divide $\frac{q-1}{\operatorname{ord}(a)}$, then with Theorem
9 the polynomial $(X^{t\cdot\frac{n}{d}\cdot p}-\zeta_{d}^{j}b)$ is
irreducible over $\mathbb{F}_{q}$ for every $0\leq j\leq d-1$. Furthermore,
the greatest common divisor of $np$ and $\frac{q-1}{\operatorname{ord}(a)}$ is
also $d$. Consequently, eq. 2 is the factorization of $X^{tnp}-a$ into monic
irreducible factors over $\mathbb{F}_{q}$ and the statement of Theorem 12
holds.

If $dp$ divides $\frac{q-1}{\operatorname{ord}(a)}$, then
$\tilde{d}:=\gcd(np,\frac{q-1}{\operatorname{ord}(a)})=dp$ and there exists
$\zeta_{\tilde{d}}\in\mathbb{F}_{q}$. Furthermore, for every $0\leq j\leq d-1$
holds $\operatorname{ord}(\zeta_{d}^{j}b)\cdot p=\operatorname{ord}(a)\cdot
d\cdot p\mid q-1$ and the polynomial $(X^{t\cdot\frac{n}{d}}-\zeta_{d}^{j}b)$
is reducible. Theorem 11 yields that there exists an element
$c_{j}\in\mathbb{F}_{q}$ such that $c_{j}^{p}=\zeta_{d}^{j}b$ and that the
factorization of $(X^{t\cdot\frac{n}{d}\cdot p}-\zeta_{d}^{j}b)$ into monic
irreducible factors over $\mathbb{F}_{q}$ is given by
$\prod_{i=0}^{p-1}(X^{t\cdot\frac{n}{d}}-\zeta_{p}^{i}c_{j})$, where
$\operatorname{ord}(\zeta_{p}^{i}c_{j})=\operatorname{ord}(\zeta_{d}^{j}b)\cdot
p=\operatorname{ord}(a)\cdot d\cdot p=\operatorname{ord}(a)\cdot\tilde{d}$.
Thus, the factorization of $X^{tnp}-a$ into monic irreducible factors over
$\mathbb{F}_{q}$ is

$X^{tnp}-a=\prod_{j=0}^{d-1}\prod_{i=0}^{p-1}(X^{t\cdot\frac{n}{d}}-\zeta_{p}^{i}c_{j})=\prod_{j=0}^{d-1}\prod_{i=0}^{p-1}(X^{t\cdot\frac{np}{\tilde{d}}}-\zeta_{p}^{i}c_{j}).$
(3)

Moreover, $c:=c_{0}$ satisfies $c^{dp}=(c^{p})^{d}=b^{d}=a$ and the
factorization of $X^{tnp}-a$ into monic irreducible factors over
$\mathbb{F}_{q}$ can also be written as:

$X^{tnp}-a=\prod_{j=0}^{\tilde{d}}(X^{t\cdot\frac{np}{\tilde{d}}}-\zeta_{\tilde{d}}^{j}c).$
(4)

Then for every $0\leq j\leq\tilde{d}-1$ holds
$\operatorname{ord}(\zeta_{\tilde{d}}^{j}c)=\operatorname{ord}(a)\cdot\tilde{d}$,
because every factor in
LABEL:eq:_factorization_X^{tnp}-a_rad(n)_mid_ord(a)_(2) corresponds to a
factor in LABEL:eq:_factorization_X^{tnp}-a_rad(n)_mid_ord(a)_(1). ∎

As in the proof of Theorem 12 we obtain the factorization of $X^{tn}-a$ for
the case $\gcd(n,\operatorname{ord}(a))=1$ by induction on the number of prime
factors of $n$. Additionally, we impose the condition $\gcd(n,t)=1$ on $n$
because otherwise the polynomials would not be reducible in every induction
step (see Corollary 10). Note that the case $\gcd(n,\operatorname{ord}(a))=1$
applies for the polynomial $X^{n}-1$ and therefore, the structure of Theorem
13 resembles the factorization given in [BGO15, Corollary 1].

######  Theorem 13.

Let $a\in\mathbb{F}_{q}^{\ast}$, $t\in\mathbb{N}$ such that $X^{t}-a$ is
irreducible over $\mathbb{F}_{q}$ and let $n\in\mathbb{N}$ such that
$\operatorname{rad}(n)\mid(q-1)$ and $\gcd(n,\operatorname{ord}(a)\cdot t)=1$.
Further, let $4\nmid tn$ or $q\equiv 1\pmod{4}$. Set
$d:=\gcd(n,\frac{q-1}{\operatorname{ord}(a)})=\gcd(n,q-1)$. Then the
factorization of $X^{tn}-a$ into monic irreducible factors over
$\mathbb{F}_{q}$ is

$\prod_{v\mid\frac{n}{d}}\prod_{\begin{subarray}{c}j=0\\\
\gcd(j,v)=1\end{subarray}}^{d-1}(X^{tv}-\zeta_{d}^{j}a^{rv}),$ (5)

where $r\in\mathbb{N}$ satisfies $rn\equiv 1\pmod{\operatorname{ord}(a)}$ and
for all applicable $v$ and $j$ holds

  1. (i)

$(\zeta_{d}^{j}a^{rv})^{\frac{n}{v}}=a$,

  2. (ii)

$\operatorname{ord}(\zeta_{d}^{j}a^{rv})=\operatorname{ord}(a)\cdot\frac{d}{\gcd(j,d)}$.

###### Proof.

Base case: If $n=p$, then the statement follows directly from Theorem 11 (ii).

Induction hypothesis: Suppose that the statement of Theorem 13 holds for
$n,d,r$ such that
$\operatorname{rad}(n)\mid(q-1),\gcd(n,\operatorname{ord}(a)\cdot
t)=1,d=\gcd(n,q-1)$ and $rn\equiv 1\pmod{\operatorname{ord}(a)}$.

Induction step ($n\rightarrow np$): Let $p$ be a prime such that $p\mid(q-1)$
and $p\nmid\operatorname{ord}(a)\cdot t$. Then there exists a positive integer
$r^{\prime}$ such that $r^{\prime}p\equiv 1\pmod{\operatorname{ord}(a)}$.
Since $\operatorname{ord}(a^{r})=\operatorname{ord}(a)$, this implies that
$a^{rr^{\prime}p}=(a^{r})^{r^{\prime}p}=a^{r}$. We set
$\tilde{r}:=rr^{\prime}$ and together with eq. 5 we obtain:

$X^{tnp}-a=\prod_{v\mid\frac{n}{d}}\prod_{\begin{subarray}{c}j=0\\\
\gcd(j,v)=1\end{subarray}}^{d-1}(X^{tvp}-\zeta_{d}^{j}a^{\tilde{r}pv}),$ (6)

where $\tilde{r}$ satisfies $\tilde{r}\cdot np=rn\cdot r^{\prime}p\equiv
1\pmod{\operatorname{ord}(a)}$. Furthermore, we have
$\operatorname{ord}(a^{\tilde{r}pv})=\operatorname{ord}(a)$, because
$(a^{\tilde{r}pv})^{\frac{n}{v}}=a$. It remains to discuss which of the
factors $(X^{tvp}-\zeta_{d}^{j}a^{\tilde{r}vp})$ are reducible. For this we
need to discern the two cases $\gcd(np,q-1)=d$ and $\gcd(np,q-1)=d\cdot p$.

Case $\gcd(np,q-1)=d$: If $\gcd(np,q-1)=d$, then $p\mid n$ but $dp\nmid q-1$
and also $\operatorname{ord}(a)\cdot d\cdot p\nmid q-1$. Let
$v\mid\frac{n}{d}$ and $0\leq j\leq d-1$ such that $\gcd(j,v)=1$. Then if
$p\mid v$, the polynomial $(X^{tvp}-\zeta_{d}^{j}a^{\tilde{r}vp})$ is
irreducible over $\mathbb{F}_{q}$ with Corollary 10. Thus, the following
expression is a factorization into irreducible factors over $\mathbb{F}_{q}$,
where we set $\tilde{v}:=vp$:

$\prod_{\begin{subarray}{c}v\mid\frac{n}{d}\\\ p\mid
v\end{subarray}}\prod_{\begin{subarray}{c}j=0\\\
\gcd(j,v)=1\end{subarray}}^{d-1}(X^{tvp}-\zeta_{d}^{j}a^{\tilde{r}vp})=\prod_{\begin{subarray}{c}\tilde{v}\mid\frac{np}{d}\\\
p^{2}\mid\tilde{v}\end{subarray}}\prod_{\begin{subarray}{c}j=0\\\
\gcd(j,\tilde{v})=1\end{subarray}}^{d-1}(X^{t\tilde{v}}-\zeta_{d}^{j}a^{\tilde{r}\tilde{v}}),$
(7)

where $\gcd(j,v)=1$ if and only if $\gcd(j,\tilde{v})=\gcd(j,vp)=1$, because
$p\mid v$. If $p\nmid v$, then with Theorem 9 the polynomial
$(X^{tvp}-\zeta_{d}^{j}a^{\tilde{r}vp})$ is irreducible if and only if
$\operatorname{ord}(\zeta_{d}^{j}a^{\tilde{r}vp})\cdot
p=\operatorname{ord}(a)\cdot\frac{d}{\gcd(j,d)}\cdot p$ does not divide
$(q-1)$. This is the case if and only if $p\nmid j$, because
$\operatorname{ord}(a)\cdot d$ divides $(q-1)$ but $\operatorname{ord}(a)\cdot
d\cdot p$ does not. Consequently, the following expression is a factorization
into irreducible factors over $\mathbb{F}_{q}$, where we set $\tilde{v}:=vp$:

$\prod_{\begin{subarray}{c}v\mid\frac{n}{d}\\\ p\nmid
v\end{subarray}}\prod_{\begin{subarray}{c}j=0\\\ \gcd(j,v)=1\\\ p\nmid
j\end{subarray}}^{d-1}(X^{tvp}-\zeta_{d}^{j}a^{\tilde{r}vp})=\prod_{\begin{subarray}{c}\tilde{v}\mid\frac{np}{d}\\\
\nu_{p}(\tilde{v})=1\end{subarray}}\prod_{\begin{subarray}{c}j=0\\\
\gcd(j,\tilde{v})=1\end{subarray}}^{d-1}(X^{t\tilde{v}}-\zeta_{d}^{j}a^{\tilde{r}\tilde{v}}).$
(8)

Let $0\leq j\leq d-1$ such that $p\mid j$. Then the polynomial
$(X^{tvp}-\zeta_{d}^{j}a^{\tilde{r}vp})$ is reducible and
$\zeta_{d}^{\frac{j}{p}}a^{\tilde{r}v}$ is an element in $\mathbb{F}_{q}$
satisfying
$(\zeta_{d}^{\frac{j}{p}}a^{\tilde{r}v})^{p}=\zeta_{d}^{j}a^{\tilde{r}vp}$.
Let $\zeta_{p}=\zeta_{d}^{\frac{d}{p}}$, then from Theorem 11 follows that its
factorization into irreducible factors over $\mathbb{F}_{q}$ is

$\prod_{i=0}^{p-1}(X^{tv}-\zeta_{p}^{i}\zeta_{d}^{\frac{j}{p}}a^{\tilde{r}v})=\prod_{i=0}^{p-1}(X^{tv}-\zeta_{d}^{\frac{d}{p}\cdot
i+\frac{j}{p}}a^{\tilde{r}v}).$

With the fact that $\\{0\leq j\leq d-1:p\mid
j\\}=\\{p\tilde{j}:0\leq\tilde{j}\leq\frac{d}{p}-1\\}$, the following
expression is a factorization into irreducible factors over $\mathbb{F}_{q}$:

$\prod_{\begin{subarray}{c}v\mid\frac{n}{d}\\\ p\nmid
v\end{subarray}}\prod_{\tilde{j}=0}^{\frac{d}{p}-1}\prod_{i=0}^{p-1}(X^{tv}-\zeta_{d}^{\frac{d}{p}\cdot
i+\tilde{j}}a^{\tilde{r}v})=\prod_{\begin{subarray}{c}v\mid\frac{np}{d}\\\
p\nmid v\end{subarray}}\prod_{j=0}^{d-1}(X^{tv}-\zeta_{d}^{j}a^{\tilde{r}v}),$
(9)

where $\operatorname{ord}(a^{\tilde{r}v})=\operatorname{ord}(a)$, because
$(a^{\tilde{r}v})^{p\frac{n}{v}}=a$. Equations (7), (8) and (9) combined yield
that if $\gcd(np,q-1)=d$ the factorization of $X^{tnp}-a$ into irreducible
factors over $\mathbb{F}_{q}$ is given by:

$\prod_{v\mid\frac{np}{d}}\prod_{\begin{subarray}{c}j=0\\\
\gcd(j,v)=1\end{subarray}}^{d-1}(X^{tv}-\zeta_{d}^{j}a^{\tilde{r}v}),$

where for all applicable $v$ and $j$ holds:

  1. (i)

$(\zeta_{d}^{j}a^{\tilde{r}v})^{\frac{np}{v}}=\zeta_{d}^{j\frac{np}{v}}a^{\tilde{r}np}=a$,
because $v\mid\frac{np}{d}$ implies $d\mid\frac{np}{v}$,

  2. (ii)

$\operatorname{ord}(\zeta_{d}^{j}a^{\tilde{r}v})=\frac{d}{\gcd(j,d)}\cdot\operatorname{ord}(a)$,
because $\gcd(d,\operatorname{ord}(a))=1$.

Case $\gcd(np,q-1)=d\cdot p$: If $\gcd(np,q-1)=dp$, then $d\cdot p\mid(q-1)$
and there exists $\zeta_{dp}\in\mathbb{F}_{q}$ such that
$\zeta_{dp}^{p}=\zeta_{d}$. Additionally, we set $\zeta_{p}:=\zeta_{dp}^{d}$.
We consider the polynomial $(X^{tvp}-\zeta_{d}^{j}a^{\tilde{r}vp})$ from eq.
6, where $v\mid\frac{n}{d}$ and $0\leq j\leq d-1$ such that $\gcd(j,v)=1$.
Since $\gcd(d\cdot p,\operatorname{ord}(a))=1$ and $dp\mid(q-1)$, the product
$\operatorname{ord}(a)\cdot d\cdot p$ divides $(q-1)$. Consequently, also
$\operatorname{ord}(\zeta_{d}^{j}a^{\tilde{r}vp})\cdot p$ divides $(q-1)$ and
with Theorem 11 the factorization of $(X^{tvp}-\zeta_{d}^{j}a^{\tilde{r}vp})$
into monic irreducible factors over $\mathbb{F}_{q}$ is

$\displaystyle\prod_{i=0}^{p-1}(X^{tv}-\zeta_{p}^{i}\zeta_{dp}^{j}a^{\tilde{r}v})=\prod_{i=0}^{p-1}(X^{tv}-\zeta_{dp}^{d\cdot
i+j}a^{\tilde{r}v}),$

because $\zeta_{dp}^{j}a^{\tilde{r}v}$ is an element of $\mathbb{F}_{q}$
satisfiying $(\zeta_{dp}^{j}a^{\tilde{r}v})^{p}=\zeta_{d}^{j}a^{\tilde{r}vp}$.

Note that $\\{di+j:0\leq i\leq p-1,0\leq j\leq d-1\\}=\\{0\leq j\leq dp-1\\}$.
Therefore, the factorization of $X^{tnp}-a$ into monic irreducible factors
over $\mathbb{F}_{q}$ is

$\prod_{v\mid\frac{n}{d}}\prod_{\begin{subarray}{c}j=0\\\
\gcd(j,v)=1\end{subarray}}^{d-1}\prod_{i=0}^{p-1}(X^{tv}-\zeta_{dp}^{di+j}a^{\tilde{r}v})=\prod_{v\mid\frac{np}{dp}}\prod_{\begin{subarray}{c}j=0\\\
\gcd(j,v)=1\end{subarray}}^{dp-1}(X^{tv}-\zeta_{dp}^{j}a^{\tilde{r}v}),$

where $\gcd(j,v)=1$ if and only if $\gcd(di+j,v)=1$, because every prime $w$
that divides $v$ must divide $n$. Since $\operatorname{rad}(n)\mid q-1$, $w$
also divides $d$. Furthermore, for all applicable $v$ and $j$, we have

  1. (i)

$(\zeta_{dp}^{j}a^{\tilde{r}v})^{\frac{np}{v}}=(\zeta_{dp}^{j}a^{\tilde{r}v})^{p\cdot\frac{n}{v}}$,
because $p$ does not divide $v$. Indeed, suppose that $p\mid v$, then with
Corollary 10 the polynomial $(X^{tvp}-\zeta_{d}^{j}a^{\tilde{r}vp})$ would not
have been reducible. Thus,
$(\zeta_{dp}^{j}a^{\tilde{r}v})^{\frac{np}{v}}=(\zeta_{d}^{j}a^{\tilde{r}vp})^{\frac{n}{v}}=a$
by induction hypothesis.

  2. (ii)

$\operatorname{ord}(\zeta_{dp}^{j}a^{\tilde{r}v})=\frac{dp}{\gcd(j,dp)}\cdot\operatorname{ord}(a)$,
because $\operatorname{ord}(a^{\tilde{r}v})=\operatorname{ord}(a)$ and
$\gcd(dp,\operatorname{ord}(a))=1$.

∎

The next theorem combines Theorems 12 and 13. It gives the complete
factorization of $X^{n}-a$ for the case $\operatorname{rad}(n)\mid(q-1)$ and
($4\nmid n$ or $q\equiv 1\pmod{4}$).

######  Theorem 14.

Let $a\in\mathbb{F}_{q}^{\ast}$ and $n\in\mathbb{N}$ such that
$\operatorname{rad}(n)\mid q-1$ and $(4\nmid n$ or $q\equiv 1\pmod{4})$. We
write $n=n_{1}\cdot n_{2},$ where
$\operatorname{rad}(n_{1})\mid\operatorname{ord}(a)$ and
$\gcd(n_{2},\operatorname{ord}(a))=1$. Further, we set
$d_{1}:=\gcd(n_{1},\frac{q-1}{\operatorname{ord}(a)})$ and
$d_{2}:=\gcd(n_{2},q-1)$. Then there exists $b\in\mathbb{F}_{q}$ such that
$b^{d_{1}}=a$ and the factorization of $X^{n}-a$ into monic irreducible
factors over $\mathbb{F}_{q}$ is

$\prod_{j=0}^{d_{1}-1}\prod_{v\mid\frac{n_{2}}{d_{2}}}\prod_{\begin{subarray}{c}i=0\\\
\gcd(i,v)=1\end{subarray}}^{d_{2}-1}(X^{\frac{n_{1}}{d_{1}}\cdot
v}-\zeta_{d_{2}}^{i}(\zeta_{d_{1}}^{j}b)^{rv}),$

where $r\in\mathbb{N}$ satisfies $rn_{2}\equiv
1\pmod{\operatorname{ord}(a)\cdot d_{1}}$ and for all applicable $j,v,i$
holds:

  1. (i)

$(\zeta_{d_{2}}^{i}(\zeta_{d_{1}}^{j}b)^{rv})^{\frac{n_{2}}{v}\cdot d_{1}}=a$,

  2. (ii)

$\operatorname{ord}(\zeta_{d_{2}}^{i}(\zeta_{d_{1}}^{j}b)^{rv})=\operatorname{ord}(a)\cdot
d_{1}\cdot\frac{d_{2}}{\gcd(i,d_{2})}$.

The number of irreducible factors of $X^{n}-a$ over $\mathbb{F}_{q}$ equals

$d_{1}\cdot d_{2}\cdot\prod_{\begin{subarray}{c}p\mid\frac{n_{2}}{d_{2}}\\\
p\text{
prime}\end{subarray}}\left(1+\nu_{p}\left(\frac{n_{2}}{d_{2}}\right)\cdot\frac{p-1}{p}\right).$

###### Proof.

From Theorem 12 follows that the factorization of $X^{n_{1}}-a$ is
$\prod_{j=0}^{d_{1}-1}(X^{\frac{n_{1}}{d_{1}}}-\zeta_{d_{1}}^{j}b)$, where
$b\in\mathbb{F}_{q}$ such that $b^{d_{1}}=a$ and
$\operatorname{ord}(\zeta_{d_{1}}^{j}b)=\operatorname{ord}(a)\cdot d_{1}$ for
all $0\leq j\leq d_{1}-1$. Since $\gcd(n_{2},\operatorname{ord}(a)\cdot
d_{1}\cdot\frac{n_{1}}{d_{1}})=1$, application of Theorem 13 yields the
factorization of $(X^{\frac{n_{1}}{d_{1}}}-\zeta_{d_{1}}^{j}b)$:

$\prod_{v\mid\frac{n_{2}}{d_{2}}}\prod_{\begin{subarray}{c}i=0\\\
\gcd(i,v)=1\end{subarray}}^{d_{2}-1}(X^{\frac{n_{1}}{d_{1}}\cdot
v}-\zeta_{d_{2}}^{i}(\zeta_{d_{1}}^{j}b)^{rv}),$

where
$(\zeta_{d_{2}}^{i}(\zeta_{d_{1}}^{j}b)^{rv})^{\frac{n_{2}}{v}}=(\zeta_{d_{1}}^{j}b)$
and
$\operatorname{ord}(\zeta_{d_{2}}^{i}(\zeta_{d_{1}}^{j}b)^{rv})=\operatorname{ord}(\zeta_{d_{1}}^{j}b)\cdot\frac{d_{2}}{\gcd(i,d_{2})}=\operatorname{ord}(a)\cdot
d_{1}\cdot\frac{d_{2}}{\gcd(i,d_{2})}$. The number of irreducible factors can
be determined with the same arguments as in the proof of [BGO15, Corollary 1
(b)]. From this proof follows directly, that for every $0\leq j\leq d_{1}-1$,
there exist $d_{2}\cdot\prod_{\begin{subarray}{c}p\mid\frac{n_{2}}{d_{2}}\\\
p\text{
prime}\end{subarray}}\left(1+\nu_{p}(\frac{n_{2}}{d_{2}})\cdot\frac{p-1}{p}\right)$
irreducible factors. Therefore, the total number of irreducible factors equals
$d_{1}\cdot d_{2}\cdot\prod_{\begin{subarray}{c}p\mid\frac{n_{2}}{d_{2}}\\\
p\text{
prime}\end{subarray}}\left(1+\nu_{p}(\frac{n_{2}}{d_{2}})\cdot\frac{p-1}{p}\right)$.
∎

######  Remark 15.

With the setup of Theorem 14, there exists a $(d_{1}d_{2})$-th primitive root
of unity in $\mathbb{F}_{q}$, because $\gcd(d_{1},d_{2})=1$. Then we can set
$\zeta_{d_{1}}=\zeta_{(d_{1}d_{2})}^{d_{2}}$ and
$\zeta_{d_{2}}=\zeta_{(d_{1}d_{2})}^{d_{1}}$ and rewrite
$\zeta_{d_{2}}^{i}(\zeta_{d_{1}}^{j}b)^{rv}=\zeta_{(d_{1}d_{2})}^{d_{1}\cdot
i+d_{2}\cdot jrv}\cdot b^{rv}$. However, this notation seemed less readable
than the expression in Theorem 14.

###  2.2 The factorization of $X^{n}-a$ for the case $\gcd(n,q)=1$

Theorem 14 combined with the following corollary, Corollary 16, allows us to
determine the factorization of $X^{n}-a$ for any positive integer $n$ such
that $\gcd(n,q)=1$ in the following way. Since $\gcd(n,q)=1$, there exists a
positive integer $w=\operatorname{ord}_{\operatorname{rad}(n)}(q)$ which
satisfies $\operatorname{rad}(n)\mid q^{w}-1$. If $4\mid n$ and $q^{w}\equiv
3\pmod{4}$, then the extension field $\mathbb{F}_{q^{2w}}$ satisfies
$q^{2w}\equiv 1\pmod{4}$ and also $\operatorname{rad}(n)\mid q^{2w}-1$. Thus,
Theorem 14 yields the factorization of $X^{n}-a$ into monic irreducible
factors over $\mathbb{F}_{q^{s}}$, where $s=w$ or $s={2w}$ respectively. The
factorization of $X^{n}-a$ over $\mathbb{F}_{q}$ can be derived from the
factorization of $X^{n}-a$ over $\mathbb{F}_{q^{s}}$ with the following
theorem. It is a corollary of Theorem 2.

######  Corollary 16.

Let $g$ be a monic polynomial over $\mathbb{F}_{q}$ and
$\prod_{R\in\mathcal{R}}R$ its factorization into monic irreducible factors
over $\mathbb{F}_{q^{w}}$ for $w\geq 1$. Then the factorization of $g$ into
monic irreducible polynomials over $\mathbb{F}_{q}$ is given by:

$\prod_{R\in\mathcal{R}/\sim}\mathrm{spin}_{q}\left[R\right],$

where $R\sim\tilde{R}$ if and only if $\tilde{R}={R}^{(j)}$ for a positive
integer $j$.

The authors of [WYF18, WY21] use the method described above to obtain their
results on the factorization of $X^{n}-1$ such that $\operatorname{rad}(n)$ is
a divisor of $q^{w}-1$ or $q^{vw}-1$. In [BRS19] the authors use this method
to factor $f(X^{n})$ such that $\gcd(n,\operatorname{ord}(f)\cdot\deg(f))=1$
and $\operatorname{rad}(n)\mid q^{w}-1$. We use this method to give the
factorization of $X^{n}-a$ for the case $\gcd(n,q)=1$ in the next theorem,
Theorem 18. For its formulation we need the following definition and fact.

Suppose that the irreducible factor $R_{i}$ is of the form
$X^{t}-\zeta_{d}^{i}$ for fixed positive integers $t$ and $d$ such that
$\gcd(d,q)=1$. Then $R_{i}\sim R_{\tilde{i}}$ if and only if
$\zeta_{d}^{i}=(\zeta_{d}^{\tilde{i}})^{q^{j}}$ for a positive integer $j$.
This condition is equivalent to $\tilde{i}\equiv i\cdot q^{j}\pmod{d}$. We
introduce the $q$-cyclotomic coset modulo $d$ containing the positive integer
$i$, which is defined as

$\mathrm{C}_{q,d}(i):=\\{i\cdot q^{j}\pmod{d}:j\geq 0\\}.$

Then $R_{i}\sim R_{\tilde{i}}$ if and only if
$\tilde{i}\in\mathrm{C}_{q,d}(i)$. Let $\mathrm{CR}_{q}(d)$ denote a complete
set of representatives of the $q$-cyclotomic cosets modulo $d$. For the proof
of Theorem 18 we also need the following fact.

######  Fact 17.

Let $G$ be a group, $a,b\in G$ and $m\in\mathbb{N}$ such that
$\gcd(m,\operatorname{ord}(a)\cdot\operatorname{ord}(b))=1$. Then
$a^{m}=b^{m}$ if and only if $a=b$.

###### Proof.

If $a=b$, then obviously $a^{m}=b^{m}$. If $a^{m}=b^{m}$, then
$1=(\frac{a}{b})^{m}$ and therefore $\operatorname{ord}(\frac{a}{b})\mid m$.
Since $\operatorname{ord}(b^{-1})=\operatorname{ord}(b)$, we know that
$(\frac{a}{b})^{\operatorname{ord}(a)\cdot\operatorname{ord}(b)}=1$ and thus
$\operatorname{ord}(\frac{a}{b})$ divides
$\operatorname{ord}(a)\cdot\operatorname{ord}(b)$. Then
$\operatorname{ord}(\frac{a}{b})=1$, because
$\gcd(m,\operatorname{ord}(a)\cdot\operatorname{ord}(b))=1$. ∎

######  Theorem 18.

Let $a\in\mathbb{F}_{q}^{\ast}$ and $n\in\mathbb{N}$ such that $\gcd(n,q)=1$
and $n=n_{1}\cdot n_{2},$ where
$\operatorname{rad}(n_{1})\mid\operatorname{ord}(a)$ and
$\gcd(n_{2},\operatorname{ord}(a))=1$. Let
$w=\operatorname{ord}_{\operatorname{rad}(n)}(q)$ and $s=w$ if $q^{w}\equiv
1\pmod{4}$ or $s=2w$ if $q^{w}\equiv 3\pmod{4}$. Further, we set
${d_{1}}^{(s)}:=\gcd(n_{1},\frac{q^{s}-1}{\operatorname{ord}(a)})$ and
${d_{2}}^{(s)}:=\gcd(n_{2},q^{s}-1)$. Then there exists
$b\in\mathbb{F}_{q^{s}}$ such that $b^{{d_{1}}^{(s)}}=a$ and the factorization
of $X^{n}-a$ into monic irreducible factors over $\mathbb{F}_{q}$ is

$\prod_{j\in\\{0,\ldots,{d_{1}}^{(s)}\\}/\sim}\;\prod_{v\mid\frac{n_{2}}{{d_{2}}^{(s)}}}\;\prod_{\begin{subarray}{c}i\in\mathrm{CR}_{q}({d_{2}}^{(s)})\\\
\gcd(i,v)=1\end{subarray}}\;\mathrm{spin}_{q}\left[R_{j,v,i}\right],$

where $j\sim\tilde{j}$ if and only if
$\zeta_{{d_{1}}^{(s)}}^{\tilde{j}}=\zeta_{{d_{1}}^{(s)}}^{jq^{m}}\;b^{(q^{m}-1)}$
for an integer $0\leq m\leq s-1$. For all applicable $j,v,i$ we have

$R_{j,v,i}=(X^{\frac{n_{1}}{{d_{1}}^{(s)}}\cdot
v}-\zeta_{{d_{2}}^{(s)}}^{i}(\zeta_{{d_{1}}^{(s)}}^{j}b)^{rv}),$

where $r$ is a positive integer satisfying $rn_{2}\equiv
1\pmod{\operatorname{ord}(a)\cdot{d_{1}}^{(s)}}$. Furthermore, with
$s_{1}:=\operatorname{ord}_{\operatorname{ord}(a)\cdot{d_{1}}^{(s)}}(q)$ holds

$\mathrm{coeffdeg}_{q}\left(R_{j,v,i}\right)=\begin{cases}s&\text{ if
}s_{1}=s,\\\ \min\\{t\in\mathbb{N}:s_{1}\mid t,\;t\mid
s,\;\frac{{d_{2}}^{(s)}}{{d_{2}}^{(t)}}\mid i\\}&\text{
otherwise.}\end{cases}$

###### Proof.

With Theorem 14 the factorization of $X^{n}-a$ over $\mathbb{F}_{q^{s}}$ is
given by:

$X^{n}-a=\prod_{j=0}^{{d_{1}}^{(s)}-1}\prod_{v\mid\frac{n_{2}}{{d_{2}}^{(s)}}}\prod_{\begin{subarray}{c}i=0\\\
\gcd(i,v)=1\end{subarray}}^{{d_{2}}^{(s)}-1}(X^{\frac{n_{1}}{{d_{1}}^{(s)}}\cdot
v}-\zeta_{{d_{2}}^{(s)}}^{i}(\zeta_{{d_{1}}^{(s)}}^{j}b)^{rv}),$

where $b\in\mathbb{F}_{q^{s}}$ such that $b^{{d_{1}}^{(s)}}=a$ and $r\cdot
n_{2}\equiv 1\pmod{\operatorname{ord}(a)\cdot{d_{1}}^{(s)}}$. Furthermore, for
all applicable $j,v,i$ holds
$\operatorname{ord}(\zeta_{{d_{2}}^{(s)}}^{i}(\zeta_{{d_{1}}^{(s)}}^{j}b)^{rv})=\operatorname{ord}(a)\cdot{d_{1}}^{(s)}\cdot\frac{{d_{2}}^{(s)}}{\gcd(i,{d_{2}}^{(s)})}.$
We define $R_{j,v,i}:=(X^{\frac{n_{1}}{{d_{1}}^{(s)}}\cdot
v}-\zeta_{{d_{2}}^{(s)}}^{i}(\zeta_{{d_{1}}^{(s)}}^{j}b)^{rv})$. Then two
irreducible factors $R_{(j,v,i)}$ and $R_{(\tilde{j},\tilde{v},\tilde{i})}$ of
$X^{n}-a$ over $\mathbb{F}_{q^{s}}$ can be factors of the same $q$-spin only
if $v=\tilde{v}$, because they need to be of the same degree. Furthermore, we
need
$\zeta_{{d_{2}}^{(s)}}^{\tilde{i}}(\zeta_{{d_{1}}^{(s)}}^{\tilde{j}}b)^{rv}=\zeta_{{d_{2}}^{(s)}}^{iq^{m}}(\zeta_{{d_{1}}^{(s)}}^{j}b)^{rvq^{m}}$
for an integer $0\leq m\leq s-1$. Since
$\gcd({d_{2}}^{(s)},\operatorname{ord}(a)\cdot{d_{1}}^{(s)})=1$, this is
equivalent to
$\zeta_{{d_{2}}^{(s)}}^{\tilde{i}}=\zeta_{{d_{2}}^{(s)}}^{iq^{m}}$ (1) and
$(\zeta_{{d_{1}}^{(s)}}^{\tilde{j}}b)^{rv}=(\zeta_{{d_{1}}^{(s)}}^{j}b)^{rvq^{m}}$
(2). For (1) to hold, that is for $\zeta_{{d_{2}}^{(s)}}^{i}$ and
$\zeta_{{d_{2}}^{(s)}}^{\tilde{i}}$ to be conjugates, $\tilde{i}$ needs to be
an element of $\mathrm{C}_{q,{d_{2}}^{(s)}}(i)$.

Concerning equation (2), we have that $v$ divides $n_{2}$ and $rn_{2}\equiv
1\pmod{\operatorname{ord}(a)\cdot{d_{1}}^{(s)}}$, which implies that
$\gcd(rv,\operatorname{ord}(a)\cdot{d_{1}}^{(s)})=1$. Then with 17 equation
(2) is equivalent to
$\zeta_{{d_{1}}^{(s)}}^{\tilde{j}}b=(\zeta_{{d_{1}}^{(s)}}^{j}b)^{q^{m}}=\zeta_{{d_{1}}^{(s)}}^{jq^{m}}\cdot
b^{(q^{m}-1)}\cdot b$. For this reason, we define a relation $\sim$ on
$\\{0,\ldots,{d_{1}}^{(s)}\\}$ as follows: $j\sim\tilde{j}$ if and only if
$\zeta_{{d_{1}}^{(s)}}^{\tilde{j}}=\zeta_{{d_{1}}^{(s)}}^{jq^{m}}b^{(q^{m}-1)}$.
Then with Corollary 16 the factorization of $X^{n}-a$ into monic irreducible
factors over $\mathbb{F}_{q}$ is

$\prod_{j\in\\{0,\ldots,{d_{1}}^{(s)}\\}/\sim}\;\prod_{v\mid\frac{n_{2}}{{d_{2}}^{(s)}}}\;\prod_{\begin{subarray}{c}i\in\mathrm{CR}_{q}({d_{2}}^{(s)})\\\
\gcd(i,v)=1\end{subarray}}\;\mathrm{spin}_{q}\left[R_{j,v,i}\right],$

where
$\mathrm{coeffdeg}_{q}\left(R_{j,v,i}\right)=\operatorname{ord}_{\operatorname{ord}(a)\cdot{d_{1}}^{(s)}\cdot\frac{{d_{2}}^{(s)}}{\gcd(i,{d_{2}}^{(s)})}}(q)$,
which depends on $i$ and is a multiple of
$\operatorname{ord}_{\operatorname{ord}(a)\cdot{d_{1}}^{(s)}}(q)=:s_{1}$.
Thus, if $s_{1}=s$, then $\mathrm{coeffdeg}_{q}\left(R_{j,v,i}\right)=s$.
Otherwise there exists a finite extension
$\mathbb{F}_{q^{s_{1}}}\leq\mathbb{F}_{q^{s_{2}}}\leq\mathbb{F}_{q^{s}}$ such
that
$\operatorname{ord}_{\operatorname{ord}(a)\cdot{d_{1}}^{(s)}\cdot\frac{{d_{2}}^{(s)}}{\gcd(i,{d_{2}}^{(s)})}}(q)=s_{2}$.
This is equivalent to $s_{1}\mid s_{2}$ and
$\frac{{d_{2}}^{(s)}}{{d_{2}}^{(s_{2})}}\mid i$ but not
$\frac{{d_{2}}^{(s)}}{{d_{2}}^{(t)}}$ for any $t<s_{2}$. Since
$\frac{{d_{2}}^{(s)}}{{d_{2}}^{(s_{2})}}\mid{d_{2}}^{(s)}$, the fraction
$\frac{{d_{2}}^{(s)}}{{d_{2}}^{(s_{2})}}$ divides every element of
$\mathrm{C}_{q,{d_{2}}^{(s)}}(i)$ and this condition is well-defined on the
set of representatives $\mathrm{CR}_{q}({d_{2}}^{(2)})$. ∎

###  2.3 The factorization of $X^{n}-a$
for the case $\operatorname{rad}(n)\mid q-1$, $4\mid n$ and $q\equiv
3\pmod{4}$

We use Theorem 18 to complete the case $\operatorname{rad}(n)\mid q-1$. If
$\operatorname{rad}(n)\mid q-1$ but $4\mid n$ and $q\equiv 3\pmod{4}$, then
$\mathbb{F}_{q^{2}}$ satisfies $q^{2}\equiv 1\pmod{4}$ and we can apply
Theorem 18 for $s=2$ to obtain the factorization of $X^{n}-a$.

######  Theorem 19.

Let $a\in\mathbb{F}_{q}^{\ast}$, $q\equiv 3\pmod{4}$ and $n\in\mathbb{N}$ such
that $\operatorname{rad}(n)\mid q-1$ and $4\mid n$. We write $n=n_{1}\cdot
n_{2},$ where $\operatorname{rad}(n_{1})\mid\operatorname{ord}(a)$ and
$\gcd(n_{2},\operatorname{ord}(a))=1$. Further, for $1\leq w\leq 2$ we set
${d_{1}}^{(w)}:=\gcd(n_{1},\frac{q^{w}-1}{\operatorname{ord}(a)})$ and
${d_{2}}^{(w)}:=\gcd(n_{2},q^{w}-1)$. Let $r$ be a positive integer satisfying
$rn_{2}\equiv 1\pmod{\operatorname{ord}(a)\cdot{d_{1}}^{(2)}}$.

Then
${d_{1}}^{(2)}\cdot{d_{2}}^{(2)}=2^{l}\cdot{d_{1}}^{(1)}\cdot{d_{2}}^{(1)}$,
where $l=\min\\{\nu_{2}(q+1),\nu_{2}(n)-1\\}\geq 1$ , and the following
statements hold:

  1. (i)

If $2\mid\operatorname{ord}(a)$, then ${d_{1}}^{(2)}=2^{l}\cdot{d_{1}}^{(1)}$
and ${d_{2}}^{(2)}={d_{2}}^{(1)}$. Furthermore, there exists
$b\in\mathbb{F}_{q^{2}}\backslash\mathbb{F}_{q}$ such that
$b^{{d_{1}}^{(2)}}=a$ and the factorization of $X^{n}-a$ into monic
irreducible factors over $\mathbb{F}_{q}$ is

$\prod_{j\in\\{0,\ldots,{d_{1}}^{(2)}-1\\}/\sim}\;\prod_{v\mid\frac{n_{2}}{{d_{2}}^{(1)}}}\;\prod_{\begin{subarray}{c}i=0\\\
\gcd(i,v)=1\end{subarray}}^{{d_{2}}^{(1)}-1}{T}_{j,v,i},$

where $j\sim\tilde{j}$ if and only if
$\zeta_{{d_{1}}^{(2)}}^{\tilde{j}}=\zeta_{{d_{1}}^{(2)}}^{jq^{m}}b^{(q^{m}-1)}$
for $m\in\\{0,1\\}$. For all applicable $j,v,i$ the trinomial $T_{j,v,i}$ is
given as:

${T}_{j,v,i}=X^{\frac{n_{1}}{2^{l-1}\cdot{d_{1}}^{(1)}}\cdot
v}-\zeta_{{d_{2}}^{(1)}}^{i}((\zeta_{{d_{1}}^{(2)}}^{j}\cdot
b)^{rv}+(\zeta_{{d_{1}}^{(2)}}^{j}b)^{rvq})\cdot
X+\zeta_{{d_{2}}^{(1)}}^{2i}(\zeta_{{d_{1}}^{(2)}}^{j}b)^{rv(q+1)}).$

The number of irreducible factors of $X^{n}-a$ over $\mathbb{F}_{q}$ equals

$\frac{{d_{1}}^{(2)}}{2}\cdot{d_{2}}^{(1)}\cdot\prod_{\begin{subarray}{c}p\mid\frac{n_{2}}{{d_{2}}^{(1)}}\\\
p\text{
prime}\end{subarray}}\left(1+\nu_{p}\left(\frac{n_{2}}{{d_{2}}^{(1)}}\right)\cdot\frac{p-1}{p}\right).$

  2. (ii)

If $2\nmid\operatorname{ord}(a)$, then ${d_{1}}^{(2)}={d_{1}}^{(1)}$ and
${d_{2}}^{(2)}=2^{l}\cdot{d_{2}}^{(1)}$. Furthermore, there exists
$b\in\mathbb{F}_{q}$ such that $b^{{d_{1}}^{(1)}}=a$ and the factorization of
$X^{n}-a$ into monic irreducible factors over $\mathbb{F}_{q}$ is

$\displaystyle\prod_{j=0}^{{d_{1}}^{(1)}-1}\;\left[\prod_{\begin{subarray}{c}v\mid\frac{n_{2}}{{d_{2}}^{(2)}}\\\
v\text{ odd}\end{subarray}}\prod_{\begin{subarray}{c}i=0\\\
\gcd(i,v)=1\end{subarray}}^{{d_{2}}^{(1)}}(X^{\frac{n_{1}}{{d_{1}}^{(1)}}\cdot
v}-\zeta_{{d_{2}}^{(1)}}^{i}(\zeta_{{d_{1}}^{(1)}}^{j}b)^{rv})\;\cdot\;\prod_{v\mid\frac{n_{2}}{{d_{2}}^{(2)}}}\;\prod_{\begin{subarray}{c}i\in\mathrm{CR}_{q}({d_{2}}^{(2)})\\\
\gcd(i,v)=1\\\ 2^{l}\nmid i\end{subarray}}T_{j,v,i}\right],$

where for all applicable $j,v,i$ the trinomial $T_{j,v,i}$ is given as:

$T_{j,v,i}=X^{2\cdot\frac{n_{1}}{{d_{1}}^{(1)}}\cdot
v}-(\zeta_{{d_{1}}^{(1)}}^{j}b)^{rv}\cdot(\zeta_{{d_{2}}^{(2)}}^{i}+\zeta_{{d_{2}}^{(2)}}^{iq})\cdot
X+(\zeta_{{d_{1}}^{(1)}}^{j}b)^{2rv}\;\zeta_{{d_{2}}^{(2)}}^{i(q+1)}.$

The number of irreducible factors of $X^{n}-a$ over $\mathbb{F}_{q}$ equals

${d_{1}}^{(1)}\cdot{d_{2}}^{(2)}\cdot\left(\frac{1}{2}+2^{l-2}\left(2+\nu_{p}\left(\frac{n_{2}}{{d_{2}}^{(2)}}\right)\right)\right)\cdot\prod_{\begin{subarray}{c}p\mid\frac{n_{2}}{{d_{2}}^{(2)}}\\\
p\text{ odd
prime}\end{subarray}}\left(1+\nu_{p}\left(\frac{n_{2}}{{d_{2}}^{(2)}}\right)\right).$

###### Proof.

If $q\equiv 3\pmod{4}$, then the extension field $\mathbb{F}_{q^{2}}$
satisfies $q^{2}\equiv 1\pmod{4}$ and $\operatorname{rad}(n)\mid q^{2}-1$ and
we can apply Theorem 18 with $s=2$. Furthermore, we have $\nu_{2}(q-1)=1$ and
$\nu_{2}(q^{2}-1)=\nu_{2}(q-1)+\nu_{2}(q+1)\geq 2$. Since
$\operatorname{rad}(n)\mid q-1$, holds

${d_{1}}^{(2)}\cdot{d_{2}}^{(2)}=\gcd(n,q^{2}-1)=2^{l}\cdot\gcd(n,q-1)=2^{l}\cdot{d_{1}}^{(1)}\cdot{d_{2}}^{(1)},$

where $l=\min\\{\nu_{2}(q+1),\nu_{2}(n)-1)\\}\geq 1$.

Case $2\mid\operatorname{ord}(a)$: Then $2\nmid n_{2}$, which implies that
${d_{2}}^{(2)}={d_{2}}^{(1)}$ and ${d_{1}}^{(2)}=2^{l}\cdot{d_{1}}^{(1)}$.
Consequently, ${d_{1}}^{(2)}$ does not divide $q-1$, $b$ is an element of
$\mathbb{F}_{q^{2}}\backslash\mathbb{F}_{q}$ and $s_{1}=s=2$. Consequently,
for all applicable $j,v,i$ the $q$-spin of $R_{j,v,i}$ is a trinomial and
given as:

$\displaystyle
T_{j,v,i}:=\mathrm{spin}_{q}\left[R_{j,v,i}\right]=R_{j,v,i}\cdot{R_{j,v,i}}^{(1)}$
$\displaystyle\quad=(X^{\frac{n_{1}}{{d_{1}}^{(2)}}\cdot
v}-\zeta_{{d_{2}}^{(1)}}^{i}(\zeta_{{d_{1}}^{(2)}}^{j}b)^{rv})(X^{\frac{n_{1}}{{d_{1}}^{(2)}}\cdot
v}-\zeta_{{d_{2}}^{(1)}}^{i}(\zeta_{{d_{1}}^{(2)}}^{j}b)^{rvq})$
$\displaystyle\quad=X^{\frac{n_{1}}{2^{l-1}\cdot{d_{1}}^{(1)}}\cdot
v}-\zeta_{{d_{2}}^{(1)}}^{i}((\zeta_{{d_{1}}^{(2)}}^{j}\cdot
b)^{rv}+(\zeta_{{d_{1}}^{(2)}}^{j}b)^{rvq})\cdot
X+\zeta_{{d_{2}}^{(1)}}^{2i}(\zeta_{{d_{1}}^{(2)}}^{j}b)^{rv(q+1)}),$

because $\zeta_{{d_{2}}^{(2)}}=\zeta_{{d_{2}}^{(1)}}$ is an element of
$\mathbb{F}_{q}$. The number of irreducible factors of $X^{n}-a$ over
$\mathbb{F}_{q}$ is exactly half the number of irreducible factors over
$\mathbb{F}_{q^{2}}$ and this number equals the number given in Theorem 14.

Case $2\nmid\operatorname{ord}(a)$: Then $2\nmid n_{1}$, which implies that
${d_{1}}^{(2)}={d_{1}}^{(1)}$ and ${d_{2}}^{(2)}=2^{l}\cdot{d_{2}}^{(1)}$.
Thus, $b$ is an element of $\mathbb{F}_{q}$ and $s_{1}=1$ and for all
applicable $i$ the degree of the coefficients of $R_{j,v,i}$ over
$\mathbb{F}_{q}$ equals

$\min\left\\{t\in\mathbb{N}:t\mid 2,\;\frac{{d_{2}}^{(2)}}{{d_{2}}^{(t)}}\mid
i\right\\}=\begin{cases}1&\text{ if }2^{l}\mid i,\\\ 2&\text{ if }2^{l}\nmid
i.\end{cases}.$

If $2^{l}\mid i$, then for all applicable $j,v$ the factor $R_{j,v,i}$ is a
monic irreducible polynomial over $\mathbb{F}_{q}$ and the following product
of monic irreducible polynomials over $\mathbb{F}_{q}$ is a factor of
$X^{n}-a$:

$\prod_{j=0}^{{d_{1}}^{(1)}-1}\prod_{v\mid\frac{n_{2}}{{d_{2}}^{(2)}}}\prod_{\begin{subarray}{c}i\in\mathrm{CR}_{q}({d_{2}}^{(2)})\\\
\gcd(i,v)=1\\\ 2^{l}\mid
i\end{subarray}}R_{j,v,i}=\prod_{j=0}^{{d_{1}}^{(1)}-1}\prod_{\begin{subarray}{c}v\mid\frac{n_{2}}{{d_{2}}^{(2)}}\\\
v\text{ odd}\end{subarray}}\prod_{\begin{subarray}{c}i=0\\\
\gcd(i,v)=1\end{subarray}}^{{d_{2}}^{(1)}}(X^{\frac{n_{1}}{{d_{1}}^{(1)}}\cdot
v}-\zeta_{{d_{2}}^{(1)}}^{i}(\zeta_{{d_{1}}^{(1)}}^{j}b)^{rv}),$

where the fact that $2^{l}\mid i$ and $\gcd(i,v)=1$ implies that $v$ is odd.
Furthermore, we can set $\zeta_{{d_{2}}^{(1)}}=\zeta_{{d_{2}}^{(2)}}^{2^{l}}$
and then
$\zeta_{{d_{2}}^{(2)}}^{i}=\zeta_{{d_{2}}^{(2)}}^{2^{l}\cdot\tilde{i}}=\zeta_{{d_{2}}^{(1)}}^{\tilde{i}}$
for an integer $0\leq\tilde{i}\leq{d_{2}}^{(1)}$. Note that for any odd $v$ we
have $\gcd(i,v)=1$ if and only if $\gcd(\tilde{i},v)=1$. Furthermore,
$|\mathrm{C}_{q,{d_{2}}^{(2)}}(i)|=1$, because
$\mathrm{coeffdeg}_{q}\left(R_{j,v,i}\right)=1$, and we can deduct that the
set $\\{i\in\mathrm{CR}_{q}({d_{2}}^{(2)}):2^{l}\mid i\\}$ equals the set
$\\{2^{l}\cdot\tilde{i}:0\leq\tilde{i}\leq{d_{2}}^{(1)}\\}$.

If $2^{l}\nmid i$, then the $q$-spin of $R_{j,v,i}$ is a trinomial and given
by:

$\displaystyle
T_{j,v,i}:=\mathrm{spin}_{q}\left[R_{j,v,i}\right]=R_{j,v,i}\cdot{R_{j,v,i}}^{(1)}$
$\displaystyle\quad=(X^{\frac{n_{1}}{{d_{1}}^{(1)}}\cdot
v}-\zeta_{{d_{2}}^{(2)}}^{i}(\zeta_{{d_{1}}^{(1)}}^{j}b)^{rv})(X^{\frac{n_{1}}{{d_{1}}^{(1)}}\cdot
v}-\zeta_{{d_{2}}^{(2)}}^{iq}(\zeta_{{d_{1}}^{(1)}}^{j}b)^{rv})$
$\displaystyle\quad\quad=X^{2\cdot\frac{n_{1}}{{d_{1}}^{(1)}}\cdot
v}-(\zeta_{{d_{1}}^{(1)}}^{j}b)^{rv}\cdot(\zeta_{{d_{2}}^{(2)}}^{i}+\zeta_{{d_{2}}^{(2)}}^{iq})\cdot
X+(\zeta_{{d_{1}}^{(1)}}^{j}b)^{2rv}\;\zeta_{{d_{2}}^{(2)}}^{i(q+1)},$

because $\zeta_{{d_{1}}^{(1)}}^{j}b$ is an element of $\mathbb{F}_{q}$ for all
$0\leq j\leq{d_{1}}^{(1)}$. The number of irreducible factors for every $0\leq
j\leq{d_{1}}^{(1)}-1$ can be determined with the same arguments as in the
proof of [BGO15, Corollary 2 (b)]. ∎

As we can see from Theorem 19 the results for more general cases become more
and more complicated. We do not present further cases such as
$\operatorname{rad}(n)\mid q^{w}-1$ for $w$ prime or the product of two primes
in detail. Instead, for these cases we refer to Theorem 18.

##  3 The factorization of $f(X^{n})$

In this section we consider again the monic irreducible polynomial
$f\in\mathbb{F}_{q}[X]$ of degree $k$. Further, $\alpha\in\mathbb{F}_{q^{k}}$
is a root of $f$. It remains to combine Theorem 3 and the factorizations of
$X^{n}-a$ from Section 2 to obtain more general factorizations of the
composition $f(X^{n})$. For this we set $g=X^{n}$ and $h=1$ in Theorem 3 and
factor the polynomial $X^{n}-\alpha$ over $\mathbb{F}_{q^{k}}$ with the
results from Section 2. Therefore, the conditions from Section 2 that are
posed on $q$ are conditions on $q^{k}$ in this section.

######  Remark 20.

The factorization of $f(X^{n})$ is given in [BRS19] for the case
$\gcd(n,\operatorname{ord}(\alpha)\cdot k)=1$. In this remark we discuss the
implications of this condition so that the differences between the existing
and our results become clear. If $\gcd(n,\operatorname{ord}(\alpha))=1$, then
there exists a positive integer $r$ such that $rn\equiv
1\pmod{\operatorname{ord}(\alpha)}$ and the element $\alpha^{r}$ satisfies
$(\alpha^{r})^{n}=\alpha$. Thus, this is a subcase of the case that there
exists an element $\beta$ in $\mathbb{F}_{q^{k}}$ such that
$\beta^{n}=\alpha$. The authors of [BRS19] claim that their results are
generalizations of the results given in [BGO15] and [WYF18]. Though this is
technically true, we would like to point out that with Proposition 5 these
factorizations could easily be obtained from the factorizations of $X^{n}-1$
in [BGO15, WYF18]. The condition $\gcd(n,k)=1$ implies that the roots of unity
appearing in the factorization of $f(X^{n})$ (or in fact of $X^{n}-\alpha$)
are elements of $\mathbb{F}_{q}$ and not $\mathbb{F}_{q^{k}}$. Since these
roots of unity are determined by ${d}^{(k)}$, this can be seen from the
following lemma and Corollary 22, which is a corollary of Lemma 21.

######  Lemma 21 ([Bey77, Proposition 1]).

Let $p$ be a prime such that $p\mid(q-1)$ and let $m$ be a positive integer.
Then

  1. (i)

If $p$ is odd, then $\nu_{p}(q^{m}-1)=\nu_{p}(q-1)+\nu_{p}(m).$

  2. (ii)

If $p=2$, then $\nu_{2}(q^{m}-1)=\begin{cases}\nu_{2}(q-1)&\text{ if }m\text{
is odd,}\\\ \nu_{2}(q-1)+\nu_{2}(m)+\nu_{2}(q+1)-1&\text{ if }m\text{ is
even,}\end{cases}$

so that $\nu_{p}(q^{m}-1)=\nu_{p}(q-1)+\nu_{p}(m)$ if $q\equiv 1\mod 4$.

######  Corollary 22.

Let $n\in\mathbb{N}$ such that $\operatorname{rad}(n)\mid q-1$ and
$\gcd(n,k)=1$. For a positive integer $w$ we set ${d}^{(w)}:=\gcd(n,q^{w}-1)$.
Then

  1. (i)

${d}^{(km)}={d}^{(m)}$ for every positive integer $m$,

  2. (ii)

${d}^{(2k)}=2^{l}\cdot{d}^{(1)}$, where
$l=\min\\{\max\\{0,\nu_{2}(n)-\nu_{2}(q-1)\\},\nu_{2}(q+1)\\}$.

###### Proof.

  1. (i)

Let $p$ be a prime divisor of $n$, then if $p$ odd, we have
$\nu_{p}(q^{km}-1)=\nu_{p}(q^{m}-1)+\nu_{p}(k)=\nu_{p}(q^{m}-1)$. If $p=2$,
then $k$ is odd, because $\gcd(n,k)=1$, and
$\nu_{2}(q^{km}-1)=\nu_{2}(q^{m}-1)$.

  2. (ii)

Let $p$ be a prime divisor of $n$, then if $p$ odd, we have
$\nu_{p}(q^{2k}-1)=\nu_{p}(q-1)+\nu_{p}(2k)=\nu_{p}(q-1)$, because $p\neq 2$
and $\gcd(n,k)=1$. If $p=2$, then
$\nu_{2}(q^{2k}-1)=\nu_{2}(q-1)+\nu_{2}(2k)+\nu_{2}(q+1)-1=\nu_{2}(q-1)+1+\nu_{2}(q+1)-1=\nu_{2}(q-1)+\nu_{2}(q+1)$.

∎

######  Remark 23.

In [BRS19, Theorem 4.1] the authors do not mention the condition
$\gcd(n,\operatorname{ord}(\alpha)\cdot k)=1$. However, without this condition
the statement of the theorem would be false. For example with Lemma 21 the
greatest common divisor $d={d}^{(2)}$ would equal
${d}^{(1)}\cdot\gcd(n,k)\cdot 2^{l}$, where
$l:=\min\\{\nu_{2}(\frac{n}{2}),\nu_{2}(q+1)\\}$ and not satisfy the equation
$d=2^{l}\cdot{d}^{(1)}$. Furthermore, the authors prove this result using
results from their section 3 and the condition
$\gcd(n,\operatorname{ord}(\alpha)\cdot k)$ is set throughout this section.

In the following we present results for the factorization of $f(X^{n})$
without the condition $\gcd(n,\operatorname{ord}(\alpha)\cdot k)=1$ on the
integer $n$. From Theorem 3 it is easy to see that the number of irreducible
factors of $f(X^{n})$ equals the number of irreducible factors of
$X^{n}-\alpha$. Therefore, we omit this information in the following results.
We start with the case $\operatorname{rad}(n)\mid q^{k}-1$ and ($4\nmid n$ or
$q^{k}\equiv 1\pmod{4}$) and combine Theorem 14 with Theorem 3.

######  Theorem 24.

Let $f\in\mathbb{F}_{q}[X]$ be an irreducible polynomial of degree $k$ and
$\alpha\in\mathbb{F}_{q^{k}}$ be a root of $f$. Further, let $n\in\mathbb{N}$
such that $\operatorname{rad}(n)\mid q^{k}-1$ and $(4\nmid n$ or $q^{k}\equiv
1\pmod{4})$. We write $n=n_{1}\cdot n_{2}$, where
$\operatorname{rad}(n_{1})\mid\operatorname{ord}(\alpha)$ and
$\gcd(n_{2},\operatorname{ord}(\alpha))=1$. Further, we set
${d_{1}}^{(k)}:=\gcd(n_{1},\frac{q^{k}-1}{\operatorname{ord}(\alpha)})$ and
${d_{2}}^{(k)}:=\gcd(n_{2},q^{k}-1)$. Then there exists
$\beta\in\mathbb{F}_{q^{k}}$ such that $\beta^{{d_{1}}^{(k)}}=\alpha$ and the
factorization of $f(X^{n})$ into monic irreducible factors over
$\mathbb{F}_{q}$ is given by:

$\displaystyle\prod_{j=0}^{{d_{1}}^{(k)}-1}\;\prod_{v\mid\frac{n_{2}}{{d_{2}}^{(k)}}}\;\prod_{\begin{subarray}{c}i=0\\\
\gcd(i,v)=1\end{subarray}}^{{d_{2}}^{(k)}-1}\;\mathrm{spin}_{q}\left[X^{\frac{n_{1}}{{d_{1}}^{(k)}}\cdot
v}-\zeta_{{d_{2}}^{(k)}}^{i}(\zeta_{{d_{1}}^{(k)}}^{j}\beta)^{rv}\right],$

where $r\in\mathbb{N}$ satisfies $rn_{2}\equiv
1\pmod{\operatorname{ord}(\alpha)\cdot{d_{1}}^{(k)}}$ and for all applicable
$j,v,i$ holds

$\mathrm{coeffdeg}_{q}\left(X^{\frac{n_{1}}{{d_{1}}^{(k)}}\cdot
v}-\zeta_{{d_{2}}^{(k)}}^{i}(\zeta_{{d_{1}}^{(k)}})\right)=k.$

The next theorem completes the case $\operatorname{rad}(n)\mid q^{k}-1$. It is
the combination of Theorem 19 and Theorem 3.

######  Theorem 25.

Let $f\in\mathbb{F}_{q}[X]$ be an irreducible polynomial of degree $k$ and
$\alpha\in\mathbb{F}_{q^{k}}$ be a root of $f$. Further, let $q^{k}\equiv
3\pmod{4}$ and $n\in\mathbb{N}$ such that $\operatorname{rad}(n)\mid q^{k}-1$
and $4\mid n$. We write $n=n_{1}\cdot n_{2}$, where
$\operatorname{rad}(n_{1})\mid\operatorname{ord}(\alpha)$ and
$\gcd(n_{2},\operatorname{ord}(\alpha))=1$. Further, for $w\in\mathbb{N}$ we
set ${d_{1}}^{(w)}:=\gcd(n_{1},\frac{q^{w}-1}{\operatorname{ord}(\alpha)})$
and ${d_{2}}^{(w)}:=\gcd(n_{2},q^{w}-1)$. Let $r$ be a positive integer
satisfying $rn_{2}\equiv
1\pmod{\operatorname{ord}(\alpha)\cdot{d_{1}}^{(2k)}}$.

Then
${d_{1}}^{(2k)}\cdot{d_{2}}^{(2k)}=2^{l}\cdot{d_{1}}^{(k)}\cdot{d_{2}}^{(k)}$,
where $l=\min\\{\nu_{2}(q^{k}+1),\nu_{2}(n)-1\\}\geq 1$, and the following
statements hold:

  1. (i)

If $2\mid\operatorname{ord}(\alpha)$, then
${d_{1}}^{(2k)}=2^{l}\cdot{d_{1}}^{(k)}$ and ${d_{2}}^{(2k)}={d_{2}}^{(k)}$.
Furthermore, there exists
$\beta\in\mathbb{F}_{q^{2k}}\backslash\mathbb{F}_{q^{k}}$ such that
$\beta^{{d_{1}}^{(2k)}}=\alpha$ and the factorization of $f(X^{n})$ into monic
irreducible polynomials over $\mathbb{F}_{q}$ is:

$\prod_{j\in\\{0,\ldots,{d_{1}}^{(2k)}-1\\}/\sim}\;\prod_{v\mid\frac{n_{2}}{{d_{2}}^{(k)}}}\;\prod_{\begin{subarray}{c}i=0\\\
\gcd(i,v)=1\end{subarray}}^{{d_{2}}^{(k)}-1}\mathrm{spin}_{q}\left[{T}_{j,v,i}\right],$

where $j\sim\tilde{j}$ if and only if
$\zeta_{{d_{1}}^{(2k)}}^{\tilde{j}}=\zeta_{{d_{1}}^{(2k)}}^{jq^{km}}\beta^{(q^{km}-1)}$
for $m\in\\{0,1\\}$. For all applicable $j,v,i$ the trinomial
$T_{j,v,i}\in\mathbb{F}_{q^{k}}[X]$ is given as:

${T}_{j,v,i}=X^{\frac{n_{1}}{2^{l-1}\cdot{d_{1}}^{(k)}}\cdot
v}-\zeta_{{d_{2}}^{(k)}}^{i}((\zeta_{{d_{1}}^{(2k)}}^{j}\cdot\beta)^{rv}+(\zeta_{{d_{1}}^{(2k)}}^{j}\beta)^{rvq^{k}})\cdot
X+\zeta_{{d_{2}}^{(k)}}^{2i}(\zeta_{{d_{1}}^{(2k)}}^{j}\beta)^{rv(q^{k}+1)}).$

  2. (ii)

If $2\nmid\operatorname{ord}(\alpha)$, then ${d_{1}}^{(2k)}={d_{1}}^{(k)}$ and
${d_{2}}^{(2k)}=2^{l}\cdot{d_{2}}^{(k)}$. Furthermore, there exists
$\beta\in\mathbb{F}_{q^{k}}$ such that $\beta^{{d_{1}}^{(k)}}=\alpha$ and the
factorization of $f(X^{n})$ into monic irreducible polynomials over
$\mathbb{F}_{q}$ is

$\displaystyle\prod_{j=0}^{{d_{1}}^{(k)}-1}\;\left[\prod_{\begin{subarray}{c}v\mid\frac{n_{2}}{{d_{2}}^{(2k)}}\\\
v\text{ odd}\end{subarray}}\prod_{\begin{subarray}{c}i=0\\\
\gcd(i,v)=1\end{subarray}}^{{d_{2}}^{(k)}}\mathrm{spin}_{q}\left[R_{j,v,i}\right]\;\cdot\;\prod_{v\mid\frac{n_{2}}{{d_{2}}^{(2)}}}\;\prod_{\begin{subarray}{c}i\in\mathrm{CR}_{q}({d_{2}}^{(2)})\\\
\gcd(i,v)=1\\\ 2^{l}\nmid
i\end{subarray}}\mathrm{spin}_{q}\left[T_{j,v,i}\right]\right],$

where for all applicable $j,v,i$ the binomial
$R_{j,v,i}\in\mathbb{F}_{q^{k}}[X]$ and trinomial
$T_{j,v,i}\in\mathbb{F}_{q^{k}}[X]$ are given as:

$\displaystyle R_{j,v,i}$ $\displaystyle=X^{\frac{n_{1}}{{d_{1}}^{(k)}}\cdot
v}-\zeta_{{d_{2}}^{(k)}}^{i}(\zeta_{{d_{1}}^{(k)}}^{j}\beta)^{rv},$
$\displaystyle T_{j,v,i}$
$\displaystyle=X^{2\cdot\frac{n_{1}}{{d_{1}}^{(k)}}\cdot
v}-(\zeta_{{d_{1}}^{(k)}}^{j}\beta)^{rv}\cdot(\zeta_{{d_{2}}^{(2k)}}^{i}+\zeta_{{d_{2}}^{(2k)}}^{iq^{k}})\cdot
X+(\zeta_{{d_{1}}^{(k)}}^{j}\beta)^{2rv}\;\zeta_{{d_{2}}^{(2k)}}^{i(q^{k}+1)}.$

The degree of the coefficients of $T_{j,v,i}$ and $R_{j,v,i}$ over
$\mathbb{F}_{q}$ equals $k$ in both (i) and (ii) for all applicable $j,v,i$.

For the general case $\gcd(n,q)=1$, the combination of Theorem 18 and Theorem
3, we need the following lemma. It shows that the $q$-spin is transitive.

######  Lemma 26.

Let $k,s$ be positive integers and $g$ be an irreducible polynomial over
$\mathbb{F}_{q^{ks}}$ such that $k\mid\mathrm{coeffdeg}_{q}\left(g\right)$,
then the $q$-spin of $g$ satisfies

$\mathrm{spin}_{q}\left[g\right]=\mathrm{spin}_{q}\left[\mathrm{spin}_{q^{k}}\left[g\right]\right].$

###### Proof.

Since $k\mid\mathrm{coeffdeg}_{q}\left(g\right)$, there exists a divisor $d$
of $s$ such that $\mathrm{coeffdeg}_{q}\left(g\right)=kd$ and
$\mathrm{coeffdeg}_{q^{k}}\left(g\right)=d$. Then if
$g=\sum_{i=0}^{m}a_{i}X^{i}$,

$\displaystyle\mathrm{spin}_{q}\left[\mathrm{spin}_{q^{k}}\left[g\right]\right]$
$\displaystyle=\mathrm{spin}_{q}\left[\prod_{j=0}^{d-1}\sum_{i=0}^{m}a_{i}^{q^{kj}}X^{i}\right]=\prod_{l=0}^{k-1}\prod_{j=0}^{d-1}\sum_{i=0}^{m}a_{i}^{q^{kj+l}}X^{i}$
$\displaystyle=\prod_{j=0}^{kd-1}\sum_{i=0}^{m}a_{i}^{q^{j}}X^{i}=\mathrm{spin}_{q}\left[g\right],$

because $q^{l}$ is a power of $\text{char}(\mathbb{F}_{q})$ and for the
coefficients of the polynomial
$\prod_{j=0}^{d-1}\sum_{i=0}^{m}a_{i}^{q^{kj+l}}X^{i}$ we can write i.e.
$(a_{i}^{q^{kj}}+a_{\tilde{i}}^{q^{k\tilde{j}}})^{q^{l}}=a_{i}^{q^{kj+l}}+a_{\tilde{i}}^{q^{k\tilde{j}+l}}$.
∎

Last but not least the next theorem, Theorem 27, gives the factorization of
$f(X^{n})$ for any positive integer $n$ such that $\gcd(n,q)=1$. As in Section
2, we can assume $\gcd(n,q)=1$ without loss of generality. Indeed, if
$\gcd(n,q)>1$, then $n=\tilde{n}\cdot\text{char}(\mathbb{F}_{q})^{l}$ and
there exists an elmement $\gamma\in\mathbb{F}_{q^{k}}$ such that
$\gamma^{\text{char}(\mathbb{F}_{q})^{l}}=\alpha$. Let $\prod_{R}R$ be the
factorization of $X^{\tilde{n}}-\gamma$ over $\mathbb{F}_{q^{k}}$, then
$(\prod_{R}R)^{\text{char}(\mathbb{F}_{q})^{l}}$ is the factorization of
$X^{n}-\alpha$ over $\mathbb{F}_{q^{k}}$. With Theorem 3 the factorization of
$f(X^{n})$ over $\mathbb{F}_{q}$ then is given by
$(\prod_{R}\mathrm{spin}_{q}\left[R\right])^{\text{char}(\mathbb{F}_{q})^{l}}$.

######  Theorem 27.

Let $n\in\mathbb{N}$ such that $\gcd(n,q)=1$ and $n=n_{1}\cdot n_{2}$, where
$\operatorname{rad}(n_{1})\mid\operatorname{ord}(\alpha)$ and
$\gcd(n_{2},\operatorname{ord}(\alpha))=1$. Let
$w=\operatorname{ord}_{\operatorname{rad}(n)}(q^{k})$. Set $s:=kw$ if $4\nmid
n$ or $q^{kw}\equiv 1\pmod{4}$, and $s:=2kw$ if $4\mid n$ and $q^{kw}\equiv
3\pmod{4}$. Further, we set
${d_{1}}^{(s)}:=\gcd(n_{1},\frac{q^{s}-1}{\operatorname{ord}(\alpha)})$ and
${d_{2}}^{(s)}:=\gcd(n,q^{s}-1)$.

Then there exists $\beta\in\mathbb{F}_{q^{ks}}$ such that
$\beta^{{d_{1}}^{(s)}}=\alpha$ and the factorization of $f(X^{n})$ into monic
irreducible factors over $\mathbb{F}_{q}$ is

$\displaystyle\prod_{j\in\\{0,\ldots,{d_{1}}^{(s)}\\}/\sim}\;\prod_{v\mid\frac{n_{2}}{{d_{2}}^{(s)}}}\;\prod_{\begin{subarray}{c}i\in\mathrm{CR}_{q^{k}}({d_{2}}^{(s)})\\\
\gcd(i,v)=1\end{subarray}}\;{=\;\mathrm{spin}_{q}\left[R_{j,v,i}\right]},$

where $j\sim\tilde{j}$ if and only if
$\zeta_{{d_{1}}^{(s)}}^{\tilde{j}}=\zeta_{{d_{1}}^{(s)}}^{jq^{km}}\beta^{q^{km}-1}$
for an integer $0\leq m\leq\frac{s}{k}-1$. For all applicable $j,v,i$ we have

$R_{j,v,i}=X^{\frac{n_{1}}{{d_{1}}^{(s)}}\cdot
v}-\zeta_{{d_{2}}^{(s)}}^{i}(\zeta_{{d_{1}}^{(s)}}^{j}\beta)^{rv},$

where $r$ is a positive integer satisfying $rn_{2}\equiv
1\pmod{\operatorname{ord}(\alpha)\cdot{d_{1}}^{(s)}}$. Furthermore, with
$s_{1}:=\operatorname{ord}_{\operatorname{ord}(\alpha)\cdot{d_{1}}^{(s)}}(q)$
holds

$\mathrm{coeffdeg}_{q}\left(R_{j,v,i}\right)=\begin{cases}s&\text{ if
}s_{1}=s,\\\ \min\\{t\in\mathbb{N}:s_{1}\mid t,t\mid
s,\frac{{d_{2}}^{(s)}}{{d_{2}}^{(t)}}\mid i\\}&\text{otherwise.}\end{cases}$

Theorem 27 can be used to obtain the explicit factorization of $f(X^{n})$ for
special cases such as $\operatorname{rad}(n)\nmid q-1$ but
$\operatorname{rad}(n)\mid q^{w}-1$ for a prime $w$. As in Section 2 we
conclude our discussion here because these results become more and more
technical without giving much further insight into the structure of the
factorization of $f(X^{n})$.

## References

  * [Als18] Zynab Alshareef “Composed Product and Factorization of Cyclotomic Polynomials over Finite Fields”, 2018
  * [Bey77] F Rudolf Beyl “Cyclic subgroups of the prime residue group” In _The American Mathematical Monthly_ 84.1 Taylor & Francis, 1977, pp. 46–48
  * [BGM93] Ian F Blake, Shuhong Gao and Ronald C Mullin “Explicit factorization of+ 1 over F p with prime p$\equiv$ 3 mod 4” In _Applicable Algebra in Engineering, Communication and Computing_ 4.2 Springer, 1993, pp. 89–94
  * [BGO15] Fabio Enrique Brochero-Martínez, Carmen Rosa Giraldo Vergara and Lilian Batista Oliveira “Explicit factorization of $x^{n}-1\in\mathbb{F}_{q}[X]$” In _Designs, Codes and Cryptography_ 77 Springer, 2015, pp. 277–286
  * [BRS19] Fabio Enrique Brochero-Martínez, Lucas Reis and Lays Silva-Jesus “Factorization of composed polynomials and applications” In _Discrete Mathematics_ 342.12 Elsevier, 2019, pp. 111603
  * [Che+12] Bocong Chen, Yun Fan, Liren Lin and Hongwei Liu “Constacyclic codes over finite fields” In _Finite Fields and Their Applications_ 18.6 Elsevier, 2012, pp. 1217–1231
  * [Coh69] Stephen D Cohen “On irreducible polynomials of certain types in finite fields” In _Mathematical Proceedings of the Cambridge Philosophical Society_ 66.2, 1969, pp. 335–344 Cambridge University Press
  * [FY07] Robert W Fitzgerald and Joseph L Yucas “Explicit factorizations of cyclotomic and dickson polynomials over finite fields” In _Arithmetic of Finite Fields: First International Workshop, WAIFI 2007, Madrid, Spain, June 21-22, 2007. Proceedings 1_ , 2007, pp. 1–10 Springer
  * [KK11] Melsik K. Kyuregyan and Gohar M. Kyureghyan “Irreducible Compositions of Polynomials over Finite Fields” In _Des. Codes Cryptography_ 61.3 USA: Kluwer Academic Publishers, 2011, pp. 301–314 DOI: 10.1007/s10623-010-9478-5
  * [Liu+17] Li Liu, Lanqiang Li, Liqi Wang and Shixin Zhu “Repeated-root constacyclic codes of length $nlp^{s}$” In _Discrete Mathematics_ 340.9 Elsevier, 2017, pp. 2250–2261
  * [LN94] Rudolf Lidl and Harald Niederreiter “Introduction to finite fields and their applications” Cambridge university press, 1994
  * [LY18] Fengwei Li and Qin Yue “The primitive idempotents and weight distributions of irreducible constacyclic codes” In _Designs, Codes and Cryptography_ 86 Springer, 2018, pp. 771–784
  * [Mey96] Helmut Meyn “Factorization of the Cyclotomic Polynomialx2n+ 1 over Finite Fields” In _Finite Fields and Their Applications_ 2.4 Elsevier, 1996, pp. 439–442
  * [MYM10] Ronald C Mullin, Joseph L Yucas and Gary Lee Mullen “A generalized counting and factoring method for polynomials over finite fields” In _Journal of Combinatorial Mathematics and Combinatorial Computing_ 72 Charles Babbage Research Centre, 2010, pp. 121–143
  * [OR21] Daniela Oliveira and Lucas Reis “On polynomials xn- 1 over binary fields whose irreducible factors are binomials and trinomials” In _Finite Fields and Their Applications_ 73 Elsevier, 2021, pp. 101837
  * [Rak+22] Supakarn Rakphon, Wutichai Chongchitmate, Jirayu Phuto and Chakkrid Klin-eam “Explicit factorization of $x^{l_{1}^{m_{1}}l_{2}^{m_{2}}l_{3}^{m_{3}}}-a$ and $a$-constacyclic codes over a finite field” In _Communications in Algebra_ 50.11 Taylor & Francis, 2022, pp. 4725–4745
  * [SF20] Zexia Shi and Fang-Wei Fu “The primitive idempotents of irreducible constacyclic codes and LCD cyclic codes” In _Cryptography and Communications_ 12.1 Springer, 2020, pp. 29–52
  * [Ste01] Greg Stein “Using the theory of cyclotomy to factor cyclotomic polynomials over finite fields” In _Mathematics of computation_ 70.235, 2001, pp. 1237–1251
  * [TW13] Aleksandr Tuxanidy and Qiang Wang “Composed products and factors of cyclotomic polynomials over finite fields” In _Designs, codes and cryptography_ 69.2 Springer, 2013, pp. 203–231
  * [Ugo16] Simone Ugolini “On an iterated construction of irreducible polynomials over finite fields of even characteristic by Kyuregyan” In _Czechoslovak Mathematical Journal_ 66 Springer, 2016, pp. 243–250
  * [Wu+17] Hongfeng Wu, Li Zhu, Rongquan Feng and Siman Yang “Explicit factorizations of cyclotomic polynomials over finite fields” In _Designs, Codes and Cryptography_ 83 Springer, 2017, pp. 197–217
  * [WW12] Liping Wang and Qiang Wang “On explicit factors of cyclotomic polynomials over finite fields” In _Designs, Codes and Cryptography_ 63 Springer, 2012, pp. 87–104
  * [WY21] Yansheng Wu and Qin Yue “Further factorization of xn- 1 over a finite field (II)” In _Discrete Mathematics, Algorithms and Applications_ 13.06 World Scientific, 2021, pp. 2150070
  * [WYF18] Yansheng Wu, Qin Yue and Shuqin Fan “Further factorization of xn- 1 over a finite field” In _Finite Fields and Their Applications_ 54 Elsevier, 2018, pp. 197–215