Fairness-aware genetic-algorithm-based few-shot classification

1.   Introduction

The study of Diophantine equations plays a very important role in number theory, and the integer solutions of Diophantine equations are widely used in cryptography and coding theory. Silverman ^[1] studied the parametric solution of equation

Li and Yuan ^[2] proved that the simultaneous Pell equations possess at most one positive integer solution under certain conditions.

A Diophantine equation of the form

is called a multivariate linear Diophantine equation, where $s, a_{1}, a_{2}, \cdots, a_{t}$ are nonzero integers and $t\geq2$. It is well known that for any given nonzero integers $a$ and $b$, there are two integers $u$ and $v$ such that

where $(a, b)$ represents the greatest common divisor of $a$ and $b$. Now we introduce some symbols associated with Eq (1.1) as follows:

That is, there exist integers $u_{1}, u_{2}, \cdots, u_{t}$ and $v_{2}, v_{3}, \cdots, v_{t-1}$ such that

Li ^[3] gave the structure of the general solution of the multivariate linear Diophantine equation.

Theorem 1.1. (^[3]) The multivariate linear Diophantine Eq (1.1) has solutions if and only if $d_{t}|s$. Furthermore, if $d_{t}|s$ and $t\geq4$, then the general solutions of Diophantine Eq (1.1) are

where $s_{i} (1\leq i\leq t-1)$ are arbitrary integers and $\delta = sd^{-1}_{t}, \bar{a}_{j} = a_{j}d^{-1}_{j}$ for $2\leq j\leq t$.

Let $\mathbb{F}_q$ be a finite field of $q$ elements with characteristic $p$, and $\mathbb{F}_{q^{n}}$ be its extension of degree $n$, where $p$ is a prime number and $n$ $\geq$ $2$ is an integer. Zhu et al. ^[4] obtained an explicit formula for the number of solutions to the equation

over $\mathbb{F}_q$. Zhao et al. ^[5] found an explicit formula for the number of solutions of the two-variable diagonal quartic equation

over $\mathbb{F}_q$.

A basis of $\mathbb{F}_{q^{n}}$ over $\mathbb{F}_q$ of the form $\{\alpha, \alpha^{q}, \cdots, \alpha^{q^{n-1}}\}$ is called a normal basis of $\mathbb{F}_{q^{n}}$ over $\mathbb{F}_q$, and $\alpha$ is called a normal element of $\mathbb{F}_{q^{n}}$ over $\mathbb{F}_q$. An irreducible polynomial $f(x)$ $\in$ $\mathbb{F}_q[x]$ is called a normal polynomial if all the roots of $f(x)$ are normal elements of $\mathbb{F}_{q^{n}}$ over $\mathbb{F}_q$. The trace of $\alpha$ is defined as

and the trace of $f(x)$ is defined to be the coefficient of $x^{n-1}$. Theorems 1.1 and 1.2 below give a simple criterion to check when an irreducible polynomial is a normal polynomial.

Theorem 1.2. (^[6]) Let $n = p^{e}$ with $e\geq1$. Then an irreducible polynomial

is a normal polynomial if and only if $a_{1}\neq0$.

Theorem 1.3. (^[7]) Let n be a prime different from p, and let q be a primitive root modulo n. Then an irreducible polynomial

is a normal polynomial if and only if $a_{1}\neq0$.

In 2001, Chang(^[8]) et al. furthermore proved that the conditions in Theorems 1.1 and 1.2 are also necessary.

Theorem 1.4. (^[8]) If every irreducible polynomial

with $a_{1}\neq0$ is a normal polynomial, then n is either a power of p or a prime different from p, and q is a primitive root modulo n.

In 2018, Huang et al. ^[9] presented a unified proof of Theorems 1.1–1.3 by comparing the number of normal polynomials and that of irreducible polynomials over $\mathbb{F}_q$.

The factorization of $x^{n}-1$ and its irreducible factors are closely related to the normal elements in $\mathbb{F}_{q^{n}}$ over $\mathbb{F}_q$ (see [10, Section 2]). Denote by $\mathfrak{F}(x^{n}-1)$ the set of all distinct monic irreducible factors of $x^{n}-1$ in a given finite field, $\Phi_{r}(x)$ a $r$-th cyclotomic polynomial, and $\varphi(\cdot)$ the Euler function. Write

where $e\geq0$ is an integer, $p$ is the characteristic of $\mathbb{F}_q$, and $p\nmid m$. Below are the known results for

Theorem 1.5. (^[11]) The following statements are equivalent:

(a) $\lvert \mathfrak{F} (x^{n}-1) \rvert = 1$.

(b) $\mathfrak{F}$($x^{n}-1$) = $\{x-1\}$.

(c) $n = p^{e}$.

Theorem 1.6. (^[11]) The following statements are equivalent:

(a) $\lvert \mathfrak{F} (x^{n}-1) \rvert = 2$.

(b) $\mathfrak{F}$($x^{n}-1$) = $\{x-1, 1+x+\dots+x^{m-1} \}$.

(c) $m$ is a prime different from $p$, and $q$ is a primitive root modulo m.

We summarize the five theorems above into the theorem below:

Theorem 1.7. The following statements are equivalent:

(a) Every irreducible polynomial of degree $n$ over $\mathbb{F}_q$ with a nonzero trace is a normal polynomial.

(b) $\mathfrak{F}$($x^{n}-1)\subseteq\{x-1, 1+x+\dots+x^{n-1} \}$.

(c) (c1) $n = p^{e}$, or

(c2) $n$ is a prime different from $p$, with $q$ being a primitive root modulo $n$.

Cao ^[11] presented a new and unified proof of Theorem 1.6 and also extended Theorem 1.6. In this paper, we give the necessary and sufficient condition for the polynomial $x^{n}-1$ to have $s$ different irreducible factors for a given positive integer $s$.

2.   Preliminaries

Lemma 2.1 indicates that factorization of $x^{n}-1$ in finite fields is closely related to the cyclotomic polynomials.

Lemma 2.1. (^[12]) Let $\mathbb{F}_q$ be a finite field of characteristic p, and let n be a positive integer not divisible by p. Then

Lemma 2.2. (^[13]) Let l be the order of a modulo m, $a^{n}\equiv1$ (mod $m$), then $l\mid n$.

Lemma 2.3. (^[12]) Let $\mathbb{F}_q$ be a finite field and $n$ a positive integer with $(q, n) = 1$. Then the cyclotomic polynomial $\Phi_{n}(x)$ factors into $\frac{\varphi(n)}{d}$ distinct monic irreducible polynomials in $\mathbb{F}_q[x]$ of the same degree d, where d is the order of q modulo n.

Lemma 2.4 is the well-known theorem about the existence of primitive roots.

Lemma 2.4. (^[14]) Let $n$ be a positive integer. Then $n$ possesses primitive roots if and only if $n$ is of the form ${\rm 2}$, ${\rm 4}$, $p^{\alpha}$, or $2p^{\alpha}$, where $p$ is an odd prime and $\alpha$ is a positive integer.

By Lemmas 2.3 and 2.4, we have the following lemma:

Lemma 2.5. The cyclotomic polynomial $\Phi_{n}(x)$ is irreducible over $\mathbb{F}_q$ if and only if $n = 2, 4, p^{\alpha}, 2p^{\alpha}$, and $q$ is a primitive root modulo $n$.

We define $v_{p}(x)$ to be the greatest power in which a prime $p$ divides $x$, that is, if $v_{p}(x) = \alpha$, then $p^{\alpha} | x$ but $p^{\alpha+1} \nmid x$. The following lemma is called the lifting the exponent lemma (LTE):

Lemma 2.6. (^[15]) Let x and y be (not necessarily positive) integers, $n$ be a positive integer, and $p$ be an odd prime such that $p | x-y$ and none of $x$ and $y$ is divisible by $p$. We have

Lemma 2.7. Let $p$ be an odd prime and $g$ be a primitive root modulo $p^{2}$, with $(g, p) = 1$. Then $g$ is a primitive root modulo $p^{l}(l\geq1)$.

Proof. We first prove that $g$ is a primitive root modulo $p^{l} (l\geq2)$ by induction on $l$. Let $g$ be a primitive root modulo $p^{l}$. The order of $g$ modulo $p^{l+1}$ is $d$. We have

which shows that

or

We next prove that

According to Euler's theorem, we have

there exists an integer $k$ such that

since $g$ is a primitive root modulo $p^{l}$, we have

Obviously, for $l\geq2$, we have

and

which shows that

where $t$ is an integer and $(k, p) = 1$. It follows that

Therefore

and $g$ is a primitive root modulo $p^{l+1}$.

We next use the LTE to prove that $g$ is a primitive root modulo $p$. The Euler's theorem shows that

since $g$ is a primitive root modulo $p^{2}$, we have

Let $h$ be the order of $g$ modulo $p$, then $h | \varphi(p)$. Similarly, we can obtain

Let $x = g^{h}$, $y = 1$, then $(p, g^{h}) = 1$, $p | g^{h}-1$. By the LTE, we have

which shows that

if $h < \varphi(p)$, then $ph < \varphi(p^{2})$, a contradiction. Thus $h = \varphi(p)$, $g$ is a primitive root modulo $p$. □

Lemma 2.8. Let $g$ be a primitive root modulo $p^{l}$. Then $g$ is a primitive root modulo $2p^{l}$, where $g$ is odd and $p$ and $l$ are the same as mentioned above.

Proof. Let $s$ be the order of $g$ modulo $2p^{l}$. Then

So we have

Since $g$ is a primitive root modulo $p^{l}$, we have $\varphi(p^{l}) | s$ and hence $\varphi(2p^{l}) | s$. So

and $g$ is a primitive root modulo $2p^{l}$. □

3.   Main result

Combining Lemmas 2.1 and 2.3, we can calculate the number of different irreducible factors for $x^{n}-1$ over $\mathbb{F}_q$. Let $m$ be a positive integer,

be its prime decomposition. If

where $e\geq0$ is an integer, and $p$ is the characteristic of $\mathbb{F}_q$ with $p\nmid m$. Then we can calculate that

where $d_{m^{\prime}}$ denotes the order of $q$ modulo $m^{\prime}$. Note that there are $\prod_{k = 1}^{l}(\alpha_{k}+1)$ items in the summation, where $\prod_{k = 1}^{l}(\alpha_{k}+1)$ is the number of factors of $m$.

Now assume that $s$ and $m$ are given positive integers, $m_{1}, \cdots, m_{t}$ are the $t$ factors of $m$. Thus, we have

If $x^{n}-1$ factors into $s$ distinct irreducible polynomials in $\mathbb{F}_q[x]$, then

there are $t$ items in the summation, the necessary and sufficient condition for

is determined as follows:

Observe $\frac{\varphi(m_{i})}{d_{m_{i}}}$ $(i = 1, 2, \cdots, t)$, and $\varphi(m_{i})$ are known; with the difference of $q$, the values of $d_{m_{i}}$ will also change, that is, the values of $\frac{\varphi(m_{i})}{d_{m_{i}}}$ will change in the different $\mathbb{F}_q$. Therefore, the $t$ items in (3.1) can be regarded as $t$ variables, and (3.1) can be regarded as the Diophantine equation with $t$ variables

Remark 3.1. Combining Lemma 2.2 and Euler's theorem, we know that $\frac{\varphi(m_{i})}{d_{m_{i}}}$ $(i = 1, \; 2, \cdots, \; t)$ are positive integers. So we only need to consider the positive integer solutions of (3.2).

Remark 3.2. The positive integers $s$ and $t$ satisfy $t\leq s$. Otherwise, if $t > s$, then it follows from Lemmas 2.1 and 2.3 that

Remark 3.3. As we all know

is a factor of $x^{n}-1$, and $x-1$ is irreducible over $\mathbb{F}_q$; the order of $q$ modulo 1 is $d_{1} = 1$. Thus, at least one positive integer solution of (3.2) whose value is 1.

We can find the positive integer solutions of (3.2). Without loss of generality, we suppose that

is the positive integer solution of (3.2), thus we have

If there exists $q$ such that the order of $q$ modulo $m_{i}$ is

then it follows from Lemma 2.3 that $\Phi_{m_{i}}(x)$ factors into

distinct monic irreducible polynomials over $\mathbb{F}_q$ of the same degree

Therefore, we have

that is, $x^{n}-1$ factors into $s$ distinct irreducible polynomials over $\mathbb{F}_q$.

In conclusion, we have the following result:

Theorem 3.4. (Main result) Let $\mathbb{F}_q$ denote the finite field of $q$ elements with characteristic $p$. Let $p$ be a prime. Let

with $e\geq0$, $p\nmid m$. Let s be a positive integer. The $t$ factors of m are $m_{1}, m_{2}, \cdots, m_{t}$ and $d_{m_{i}}$ denotes the order of q modulo $m_{i}$. Then

if and only if

is a solution to the Diophantine equation

Proof. We first assume that

is the solution of the Diophantine equation

By Lemmas 2.1 and 2.3, we have

and $\Phi_{m_{i}}(x)$ factors into

distinct monic irreducible polynomials in $\mathbb{F}_q[x]$ of the same degree

Hence, we obtain

Suppose

According to Lemma 2.3, we have

So

is the solution of the Diophantine equation

□

4.   Applications

We apply Theorem 3.4 to deduce Theorem 1.6. Note that Theorem 1.5 is trivial. Recall that

where $e\geq0$ is an integer and $p$ is the characteristic of $\mathbb{F}_q$ with $p\nmid m$.

For Theorem 1.6

we know that $m$ has two factors; thus, $m$ is a prime different from $p$,

The unique positive integer solution of the Diophantine equation

is

Since

and by Theorem 3.4, we have

that is, $d_{m} = \varphi(m),$ $q$ is a primitive root modulo $m$. It follows from Lemma 2.5 that the cyclotomic polynomial $\Phi_{m}(x)$ is irreducible over $\mathbb{F}_q$. Thus

The necessary and sufficient conditions for

are given, respectively, below: for

we know that $t\leq3$, where $t$ is the number of factors of $m$.

Case 1. If $m$ has three factors, then $m = r^{2}$, where $r$ is a prime different from $p$.

The unique positive integer solution of the Diophantine equation

is

By Theorem 3.4, we have

that is,

$q$ is a primitive root modulo $r$ and $r^{2}$. Recall Lemma 2.7: If $q$ is a primitive root modulo $r^{2}$, then $q$ is a primitive root modulo $r$. Cyclotomic polynomials $\Phi_{r}(x)$ and $\Phi_{r^{2}}(x)$ are irreducible over $\mathbb{F}_q$. Thus

Case 2. If $m$ has two factors, then $m = r$,

The positive integer solution of the Diophantine equation

is $x_{1} = 1$, $x_{2} = 2$. Hence, we obtain

that is,

the order of $q$ modulo $r$ is $\frac{\varphi(r)}{2}$. According to Lemma 2.3, the cyclotomic polynomial $\Phi_{r}(x)$ factors into

distinct monic irreducible polynomials in $\mathbb{F}_q[x]$ of the same degree

Thus

In conclusion, we have the following result:

Theorem 4.1. The following statements are equivalent:

(a) $\lvert \mathfrak{F} (x^{n}-1) \rvert = 3$.

(b) (b1) $\mathfrak{F}$($x^{n}-1$) = $\{x-1, f_{1}(x), f_{2}(x)\}$, where $m = r$,

(b2) $\mathfrak{F}$($x^{n}-1$) = $\{x-1, \Phi_{r}(x), \Phi_{r^{2}}(x)\}$, where $m = r^{2}$.

(c) (c1) $m = r$, and the order of $q$ modulo $r$ is $\frac{\varphi(r)}{2}$.

(c2) $m = r^{2}$, and $q$ is a primitive root modulo $r^{2}$.

For

we know that $t\leq4$, where $t$ is the number of factors of $m$. In the remaining part of this paper, we always assume that $r$ is an odd prime different from $p$.

If $m$ has four factors, then the possible values of $m$ are $r^{3}$, $2r$, $p_{1}p_{2}$ or 8, where $p_{1}$ and $p_{2}$ are odd primes different from $p$. The unique positive integer solution of the Diophantine equation

is

Case 1. If $m = r^{3}$, then

and we have

that is, $q$ is a primitive root modulo $r^{l}, l = 1, 2, 3$, which requires that $q$ is a primitive root modulo $r^{2}$. The cyclotomic polynomials $\Phi_{r}(x)$, $\Phi_{r^{2}}(x)$, and $\Phi_{r^{3}}(x)$ are irreducible over $\mathbb{F}_q$. Thus

Case 2. If $m = 2r$, then

and we have

that is, $q$ is a primitive root modulo $r$ and $2r$. Recall Lemma 2.8: If $q$ is a primitive root modulo $r$, then $q$ is a primitive root modulo $2r$. The cyclotomic polynomials $\Phi_{r}(x)$ and $\Phi_{2r}(x)$ are irreducible over $\mathbb{F}_q$. Obviously, the order of $q$ modulo 2 is $d_{2} = 1$, and

is irreducible over $\mathbb{F}_q$. Thus

Case 3. If $m = p_{1}p_{2}$, then

and we have

It follows from Lemma 2.4 that $p_{1}p_{2}$ has no primitive root, which contradicts

The cyclotomic polynomial $\Phi_{p_{1}p_{2}}(x)$ is reducible over $\mathbb{F}_q$. Thus

Case 4. If $m = 8$, then

Since 8 has no primitive root, $\Phi_{8}(x)$ is reducible over $\mathbb{F}_q$. Thus

If $m$ has three factors, then the possible values of $m$ are $r^{2}$ or $4$. The positive integer solution of the equation

is

Case 1. If $m = r^{2}$, then

and we have

or

For the former, the order of $q$ modulo $r$ is

and $q$ is a primitive root modulo $r^{2}$, which is impossible by Lemma 2.7. For the latter, $q$ is a primitive root modulo $r$, and the order of $q$ modulo $r^{2}$ is $\frac{\varphi(r^{2})}{2}$. It follows that

Thus $\varphi(r) | \frac{r\varphi(r)}{2}$. Since $r$ is an odd prime, $\frac{r}{2}$ is not an integer, and the divisibility is not valid.

Case 2. If $m = 4$, then

and we have

that is, the order of $q$ modulo 4 is

The cyclotomic polynomial

factors into

distinct monic irreducible polynomials in $\mathbb{F}_q[x]$ of the same degree, $d_{4} = 1$. Thus

If $m$ has two factors, then $m = r$,

The positive integer solution of the Diophantine equation

is $x_{1} = 1$, $x_{2} = 3$. Hence, we have

that is, the order of $q$ modulo $r$ is $\frac{\varphi(r)}{3}$. The cyclotomic polynomial $\Phi_{r}(x)$ factors into three distinct monic irreducible polynomials in $\mathbb{F}_q[x]$ of the same degree $\frac{\varphi(r)}{3}$. Thus

In conclusion, we have the following result:

Theorem 4.2. The following statements are equivalent:

(a) $\lvert \mathfrak{F} (x^{n}-1) \rvert = 4$.

(b) (b1) $\mathfrak{F}$($x^{n}-1$) = $\{x-1, f_{1}(x), f_{2}(x), f_{3}(x)\}$, where $m = r$,

(b2) $\mathfrak{F}$($x^{n}-1$) = $\{x-1, \Phi_{r}(x), \Phi_{r^{2}}(x), \Phi_{r^{3}}(x)\}$, where $m = r^{3}$.

(b3) $\mathfrak{F}$($x^{n}-1$) = $\{x-1, x+1, \Phi_{r}(x), \Phi_{2r}(x)\}$, where $m = 2r$.

(b4) $\mathfrak{F}$($x^{n}-1$) = $\{x-1, x+1, x+e_{1}, x+e_{2}\}$, where $m = 4$, $e_{1}$ and $e_{2}$ are integers.

(c) (c1) $m = r$, and the order of $q$ modulo $r$ is $\frac{\varphi(r)}{3}$.

(c2) $m = r^{3}$, and $q$ is a primitive root modulo $r^{2}$.

(c3) $m = 2r$, and $q$ is a primitive root modulo $r$.

(c4) $m = 4$, and the order of $q$ modulo $4$ is $1$.

For

we know that $t\leq5$, where $t$ is the number of factors of $m$.

If $m$ has five factors, then the possible values of $m$ are $r^{4}$ or 16. The unique positive integer solution of the equation

is

Case 1. If $m = r^{4}$, then

and we have

that is, $q$ is a primitive root modulo $r^{l}, l = 1, 2, 3, 4$, which requires that $q$ is a primitive root modulo $r^{2}$. The cyclotomic polynomials $\Phi_{r}(x), \Phi_{r^{2}}(x), \Phi_{r^{3}}(x)$, and $\Phi_{r^{4}}(x)$ are irreducible over $\mathbb{F}_q$. Thus

Case 2. If $m = 16$, then

Since 8 and 16 have no primitive root, we know that $\Phi_{8}(x)$ and $\Phi_{16}(x)$ are reducible over $\mathbb{F}_q$. Thus

If $m$ has four factors, then the possible values of $m$ are $r^{3}, 8, 2r$ or $p_{1}p_{2}$. The positive integer solution of the equation

is

Case 1. If $m = r^{3}$, then

It follows from Lemma 2.7 that

and

that is, $q$ is a primitive root modulo $r^{3}$, the order of $q$ modulo $r^{2}$ is $\frac{\varphi(r^{2})}{2}$. It follows that

Since $q$ is a primitive root modulo $r^{3}$, we have

By Lemma 2.6, we have

which is a contradiction. Thus, if $m = r^{3}$, then

Case 2. If $m = 8$, then

and we have

that is, $q$ is a primitive root modulo 4, which means $q$ is congruent to 3 modulo 4, therefore the order of $q$ modulo 8 is

$\Phi_{4}(x)$ is irreducible over $\mathbb{F}_q$, and $\Phi_{8}(x)$ factors into

distinct monic irreducible polynomials in $\mathbb{F}_q[x]$ of the same degree $2$. Thus

Case 3. If $m = 2r$, then

It follows from Lemma 2.8 that

that is, $q$ is a primitive root modulo $2r$, and the order of $q$ modulo $r$ is $\frac{\varphi(r)}{2}$, $\Phi_{2r}(x)$ is irreducible over $\mathbb{F}_q$ and $\Phi_{r}(x)$ factors into

distinct monic irreducible polynomials in $\mathbb{F}_q[x]$ of the same degree $\frac{\varphi(r)}{2}$. Thus

Case 4. If $m = p_{1}p_{2}$, then

Since $p_{1}p_{2}$ has no primitive root, we have

that is, $q$ is a primitive root modulo $p_{1}$ and $p_{2}$, and the order of $q$ modulo $p_{1}p_{2}$ is $\frac{\varphi(p_{1}p_{2})}{2}$, $\Phi_{p_{1}}(x)$ and $\Phi_{p_{2}}(x)$ are irreducible over $\mathbb{F}_q$, and $\Phi_{p_{1}p_{2}}(x)$ factors into

distinct monic irreducible polynomials in $\mathbb{F}_q[x]$ of the same degree $\frac{\varphi(p_{1}p_{2})}{2}$. Thus

If $m$ has three factors, then the possible values of $m$ are $4$ or $r^{2}$. If $m = 4$, there are at most four distinct irreducible factors for $x^{n}-1$. Thus

If $m = r^{2}$, then

The positive integer solutions of the equation

are

For the former, we have

that is, the order of $q$ modulo $r$ is $\frac{\varphi(r)}{2}$ and the order of $q$ modulo $r^{2}$ is $\frac{\varphi(r^{2})}{2}$, $\Phi_{r}(x)$, and $\Phi_{r^{2}}(x)$ factor into $2$ distinct monic irreducible polynomials in $\mathbb{F}_q[x]$. Thus

For the latter, it follows from Lemma 2.7 that

that is, $q$ is a primitive root modulo $r$, and the order of $q$ modulo $r^{2}$ is $\frac{\varphi(r^{2})}{3}$, $\Phi_{r}(x)$ is irreducible over $\mathbb{F}_q$ and $\Phi_{r^{2}}(x)$ factors into $3$ distinct monic irreducible polynomials in $\mathbb{F}_q[x]$. Thus

If $m$ has two factors, then

The positive integer solution of the equation $x_{1}+x_{2} = 5$ is $x_{1} = 1, x_{2} = 4$. Hence, we have

that is, the order of $q$ modulo $r$ is $\frac{\varphi(r)}{4}$. The cyclotomic polynomial $\Phi_{r}(x)$ factors into four distinct monic irreducible polynomials in $\mathbb{F}_q[x]$. Thus

In conclusion, we obtain the following result:

Theorem 4.3. The following statements are equivalent:

(a) $\lvert \mathfrak{F} (x^{n}-1) \rvert = 5$.

(b) (b1) $\mathfrak{F}$($x^{n}-1$) = $\{x-1, \Phi_{r}(x), \Phi_{r^{2}}(x), \Phi_{r^{3}}(x), \Phi_{r^{4}}(x)\}$, where $m = r^{4}$.

(b2) $\mathfrak{F}$($x^{n}-1$) = $\{x-1, x+1, \Phi_{4}(x), f_{1}(x), f_{2}(x)\}$, where $m = 8$,

(b3) $\mathfrak{F}$($x^{n}-1$) = $\{x-1, x+1, g_{1}(x), g_{2}(x), \Phi_{2r}(x)\}$, where $m = 2r$,

(b4) $\mathfrak{F}(x^{n}-1)$ = $\{x-1, \Phi_{p_{1}}(x), \Phi_{p_{2}}(x), h_{1}(x), h_{2}(x)\}$, where $m = p_{1}p_{2}$,

(b5) $\mathfrak{F}$($x^{n}-1$) = $\{x-1, k_{1}(x), k_{2}(x), r_{1}(x), r_{2}(x)\}$, where $m = r^{2}$,

Or $\mathfrak{F}$($x^{n}-1$) = $\{x-1, \Phi_{r}(x), u_{1}(x), u_{2}(x), u_{3}(x)\}$, where $m = r^{2}$,

(b6) $\mathfrak{F}$($x^{n}-1$) = $\{x-1, v_{1}(x), v_{2}(x), v_{3}(x), v_{4}(x)\}$, where $m = r$,

(c) (c1) $m = r^{4}$, and $q$ is a primitive root modulo $r^{2}$.

(c2) $m = 8$, $q$ is a primitive root modulo ${\rm 4}$, and the order of $q$ modulo ${\rm 8}$ is ${\rm 2}$.

(c3) $m = 2r$, the order of $q$ modulo $r$ is $\frac{\varphi(r)}{2}$ and $q$ is a primitive root modulo $2r$.

(c4) $m = p_{1}p_{2}$, the order of $q$ modulo $p_{1}p_{2}$ is $\frac{\varphi(p_{1}p_{2})}{2}$, and $q$ is a primitive root modulo $p_{1}$ and $p_{2}$.

(c5) $m = r^{2}$, the order of $q$ modulo $r$ is $\frac{\varphi(r)}{2}$ and the order of $q$ modulo $r^{2}$ is $\frac{\varphi(r^{2})}{2}$; or $q$ is a primitive root modulo $r$ and the order of $q$ modulo $r^{2}$ is $\frac{\varphi(r^{2})}{3}$.

(c6) $m = r$, and the order of $q$ modulo $r$ is $\frac{\varphi(r)}{4}$.

5.   Examples

In this final section, we provide two examples.

Example 5.1. Let $\mathbb{F}_q$ denote the finite field of $q$ elements with characteristic $p$. Let $p$ be a prime, let $r$ be a prime different from $p$, and let $n = r^{l}p^{e}$, with $l\geq1$, $e\geq0$. Denote by $\mathfrak{F}(x^{n}-1)$ the set of all distinct monic irreducible factors of $x^{n}-1$ in a given finite field. Given a positive integer $s$, we consider the special case for

Since $n = r^{l}p^{e}$,

The unique positive integer solution of the equation

is

where $d_{r^{i}}$ denotes the order of q modulo $r^{i}$ $(i = 0, 1, \cdots, l)$. That is, $q$ is a primitive root modulo $r^{j}$ $(j = 1, 2, \cdots, l)$. Recall Lemma 2.7 that if $q$ is a primitive root modulo $r^{2}$, then $q$ is a primitive root modulo $r^{j}$ $(j = 1, 2, \cdots, l)$. Cyclotomic polynomials $\Phi_{r^{j}}(x)$ $(j = 1, 2, \cdots, l)$ are irreducible over $\mathbb{F}_q$.

In conclusion, if $q$ is a primitive root modulo $r^{2}$, then

Example 5.2. We factor polynomial $x^{25}-1$ into distinct monic irreducible polynomials over $\mathbb{F}_{7}$. Since $25 = 5^{2}$,

We first calculate

where $7$ is a primitive root modulo $5$, thus

is irreducible over $\mathbb{F}_{7}$.

We next calculate

the order of $\ 7$ modulo $25$ is $4$, thus

factors into

distinct monic irreducible polynomials over $\mathbb{F}_{7}$ of the same degree $4$,

respectively.

Thus

and

6.   Conclusions

{Let $\mathbb{F}_q$ be the finite field of $q$ elements, and $\mathbb{F}_{q^{n}}$ be its extension of degree $n$. Denote by $\mathfrak{F}(x^{n}-1)$ the set of all distinct monic irreducible factors of the polynomial $x^{n}-1$ in the finite field $\mathbb{F}_q$. Given a positive integer $s$, we use the properties of cyclotomic polynomials in finite fields and results from the Diophantine equations to provide the sufficient and necessary condition for

As an application, we also obtain the sufficient and necessary conditions for

Author contributions

Weitao Xie: the first draft of the manuscript; Jiayu Zhang: preliminaries collection and analysis; Wei Cao: originally raised the problem and commented on previous versions of the manuscript. All authors contributed to the study conception and design. All authors read and approved the final manuscript.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

The authors thank the anonymous referees for their helpful comments that improved the quality of the manuscript. This work was jointly supported by the Fujian Provincial Natural Science Foundation of China (Grant No. 2022J02046), and Fujian Key Laboratory of Granular Computing and Applications (Minnan Normal University).

Conflict of interest

All authors declare no conflicts of interest in this paper.