# The Concept ofq-Cycle and Applications

Authors: Umarin Pintoptang; Suton Tadee; Vichian Laohakosol
Journal: Journal of Discrete Mathematics
 (2014)

---

## Abstract

The concept ofq-cycle is investigated for its properties and applications. Connections
with irreducible polynomials over a finite field are established with emphases on the
notions of order and degree. The results are applied to deduce new results about
primitive and self-reciprocal polynomials.


---

## Body

## 1. Introduction

Let𝔽
q denote the finite field of q elements and let N
∈
ℕ, gcd
(
q
,
N
)
=
1. Let a
0
,
a
1
,
…
,
a
ℓ
-
1 be ℓ  distinct numbers chosen from ℤ
N
:
=
{
0,1
,
…
,
N
-
1
}. If
(1)
a
i
q
≡
a
i
+
1
mod
⁡
N
(
i
=
0,1
,
…
,
ℓ
-
2
)
,
(
a
0
q
ℓ
)
≡
a
ℓ
-
1
q
≡
a
0
mod
⁡
N
,
then we say that (
a
0
,
a
1
,
…
,
a
ℓ
-
1
) forms a q-cycle mod N
with leading element
a
0, abbreviated by q
(
a
0
)-cycle(
N
) or q-cycle(
N
) when the leading element in the cycle is immaterial, and call ℓ the length of this q
(
a
0
)-cycle(
N
). The notion of q-cycles was introduced by Wan in his book [1, page 203]. Since q
o
N
(
q
)
≡
1
mod
⁡
N, where o
N
(
q
) is the order of q in ℤ
N
*
:
=
ℤ
N
∖
{
0
} (the multiplicative group of nonzero integers modulo N), it clearly follows that each q
(
a
)-cycle(
N
) always has a unique length ℓ which is the least positive integer ℓ for which a
≡
a
q
ℓ
mod
⁡
N. Observe that q-cycles are nothing but ℤ-orbits q
ℤ
a
,
a
∈
ℤ
N; that is, 1
∈
ℤ acts on ℤ
N by multiplication with q. The concept of q-cycles is important because of the following connections with irreducible polynomials.(A) (see [1, Theorem 9.11]) Let α be a primitive Nth root of unity (if the order of q in ℤ
N
* is m, then there exists a primitive Nth root of unity in 𝔽
q
m). If (
a
0
,
a
1
,
…
,
a
ℓ
-
1
) is a q-cycle(
N
), then
(2)
h
(
x
)
=
(
x
-
α
a
0
)
(
x
-
α
a
1
)
⋯
(
x
-
α
a
ℓ
-
1
)
is a monic irreducible factor of x
N
-
1 in 𝔽
q
[
x
]. Conversely, if h
(
x
) is a monic irreducible factor of x
N
-
1 in 𝔽
q
[
x
], then all the roots of h
(
x
) are powers of α whose exponents form a q-cycle(
N
). We henceforth refer to these two facts as the
α
-correspondence.(B) (see [1, Corollary 9.12]) The number of distinct irreducible polynomials dividing x
N
-
1 in 𝔽
q
[
x
] is equal to the number of q-cycles(
N
) formed with the leading N elements taken from {
0,1
,
…
,
N
-
1
}.Our objectives here are to illustrate the versatility ofq-cycles by using them to prove new results about irreducible polynomials. General properties of q-cycles are given in the next section; specific details in two special cases corresponding to N
=
q
n
-
1
,
q
m
+
1 are worked out for applications to primitive and self-reciprocal polynomials in the last section. Section 3 deals with results about the order of a polynomial, while Section 4 does the same for the degree of a polynomial. Section 5 shows that knowing a q-cycle is equivalent to knowing all coefficients of the corresponding polynomial (2). The last section provides applications of q-cycles to primitive and self-reciprocal polynomials.Notation and Terminology. Throughout, we fix the following symbols and their meanings.(i)
pis a fixed prime, q is a power of p, and 𝔽
q is the finite field with q elements.
(ii)
N is a fixed positive integer such that gcd
(
q
,
N
)
=
1.
(iii)
d
:
=
d
(
N
) is the number of (positive integer) divisors of N.
(iv)
N
=
N
1
>
N
2
>
⋯
>
N
d
=
1 (all divisors of N).
(v)
Forn
∈
ℕ, the Möbius function μ is defined by
(3)
μ
(
n
)
=
{
1
,
if
n
=
1
,
(
-
1
)
k
,
if
n
is
a
squarefree
product
of
k
distinct
primes
,
0
,
if
n
is
not
squarefree
.
(vi)
Forn
∈
ℕ, the Euler's function φ
(
n
) is the number of integers k
∈
{
1,2
,
…
,
n
} with gcd
(
k
,
n
)
=
1.
(vii)
ForM
∈
ℕ, denote by o
M
(
q
) the order of q in ℤ
M
*
:
=
ℤ
M
∖
{
0
}; that is,
(4)
q
o
M
(
q
)
≡
1
mod
⁡
M
,
but
q
i
≢
1
mod
⁡
M
∀
i
∈
ℕ
,
i
<
o
M
(
q
)
.
(viii)
Forr
∈
{
1,2
,
…
,
d
}, set 𝒞
N
r
=
{
q
-cycles
(
N
r
)
}, the set of all q-cycles mod
⁡ N
r.


## 2. Properties ofq-Cycles

Let(
a
0
,
a
1
,
…
,
a
ℓ
-
1
) be a q
(
a
0
)-cycle(
N
). It is easy to see that ℤ
N can be decomposed into a finite union of disjoint q-cycles(
N
), namely,
(5)
ℤ
N
=
(
0
)
∪
(
1
,
q
,
q
2
,
…
,
q
o
N
(
q
)
-
1
)
⋃
a
∈
ℤ
N
∖
{
0,1
}
‍
(
a
,
a
q
,
a
q
2
,
…
)
.
Since q
o
N
(
q
)
≡
1
mod
⁡
N and a
q
o
N
(
q
)
≡
a
mod
⁡
N for all a
∈
ℤ
N, each q-cycle(
N
) is of length ≤
o
N
(
q
) with the one containing 1 having the largest length. We collect in our first theorem further properties of q-cycles, whose straightforward proofs are omitted.Theorem 1.
Leta, b
∈
ℤ
N, N
0
:
=
ℕ
∪
{
0
}. (i)
The elementb
∈
q
(
a
)-cycle(
N
) if and only if b
≡
a
q
m
mod
⁡
N for some m
∈
ℕ
0.
(ii)
Twoq-cycles, q
(
a
)-cycle(
N
) and q
(
b
)-cycle(
N
), are identical if and only if b
∈
q
(
a
)-cycle(
N
).
(iii)
Forb
∈
ℤ
N
*, each q
(
b
)-cycle(
N
) has length ℓ if and only if N
/
gcd
(
b
,
N
) divides q
ℓ
-
1 but does not divide q
-
1
,
q
2
-
1
,
…
,
q
ℓ
-
1
-
1 (if ℓ
=
1, only the first divisibility needs to be checked). The q
(
0
)-cycle(
N
) has length 1.
(iv)
The length of eachq-cycle(
N
) divides o
N
(
q
).
(v)
Ifb
∈
ℤ
N is such that gcd
⁡
(
b
,
N
)
=
N
r, then the q
(
b
)-cycle(
N
) has length o
N
/
N
r
(
q
), and there are altogether φ
(
N
/
N
r
)
/
o
N
/
N
r
(
q
) distinct such q-cycles. In particular, if b
∈
ℤ
N is such that gcd
⁡
(
b
,
N
)
=
1, then the q
(
b
)-cycle(
N
) has length o
N
(
q
), and there are altogether φ
(
N
)
/
o
N
(
q
) distinct q-cycles with length o
N
(
q
).
(vi)
The length of anyq-cycle(
N
) is of the form o
N
r
(
q
) for some r
∈
{
1
,
…
,
d
}.
(vii)
The number ofq-cycles(
N
) of length ℓ is (
1
/
ℓ
)
∑
1
≤
r
≤
d
,
o
N
r
(
q
)
=
ℓ
‍
φ
(
N
r
).
(viii)
The total number ofq-cycles(
N
) is |
𝒞
N
|
=
∑
1
≤
r
≤
d
(
φ
(
N
r
)
/
o
N
r
(
q
)
)
‍ (|
·
| signifies the number of elements in the set).


### 2.1. Two Special Cases

There are two particular casesN
=
q
n
-
1 and N
=
q
m
+
1, which are closely related to primitive and self-reciprocal and will be needed in the last section.


#### 2.1.1. The CaseN
=
q
n
-
1

WhenN
=
q
n
-
1
(
n
∈
ℕ
), more precise information is now derived.Theorem 2.
Letn
∈
ℕ. Then (i)
o
q
n
-
1
(
q
)
=
n;
(ii)
n is the largest length among q-cycles(
q
n
-
1
) and any other length of q-cycles(
q
n
-
1
) divides n;
(iii)
the number ofq-cycles(
q
n
-
1
) having length ℓ is equal to
(6)
1
ℓ
∑
1
≤
r
≤
d
o
N
r
(
q
)
=
ℓ
‍
φ
(
N
r
)
=
{
q
-
1
i
f
ℓ
=
1
1
ℓ
∑
k
∣
ℓ
‍
μ
(
k
)
q
ℓ
/
k
i
f
ℓ
>
1
.Proof.
Assertions (i) and (ii) are immediate from the definition and Theorems1(iii)-(iv). To verify (iii), observe that if ℓ
=
1, then it is easily checked that all the q-cycles(
q
n
-
1
) of length 1 are those starting with 0, A
:
=
q
n
-
1
+
q
n
-
2
+
⋯
+
q
+
1,2
A
,
…
,
(
q
-
2
)
A whose total number is q
-
1. Assume now that ℓ
>
1 and that the assertion holds up to ℓ
-
1. From Theorem 1(vii), the number of q-cycles(
q
n
-
1
) having length ℓ is (
1
/
ℓ
)
∑
1
≤
r
≤
d
,
o
N
r
(
q
)
=
ℓ
‍
φ
(
N
r
). Thus, to prove the desired result, we only need to verify that
(7)
∑
1
≤
r
≤
d
o
N
r
(
q
)
=
ℓ
‍
φ
(
N
r
)
=
∑
k
∣
ℓ
‍
μ
(
k
)
q
ℓ
/
k
.
Consider
(8)
∑
1
≤
r
≤
d
o
N
r
(
q
)
=
ℓ
‍
φ
(
N
r
)
=
∑
N
r
∣
(
q
ℓ
-
1
)
N
r
∤
(
q
s
-
1
)
∀
s
∣
ℓ
,
1
≤
s
<
ℓ
‍
φ
(
N
r
)
=
∑
N
r
∣
(
q
ℓ
-
1
)
‍
φ
(
N
r
)
-
∑
N
r
∣
(
q
s
-
1
)
∀
s
∣
ℓ
,
1
≤
s
<
ℓ
‍
φ
(
N
r
)
=
q
ℓ
-
1
-
∑
N
r
∣
(
q
s
-
1
)
∀
s
∣
ℓ
,
1
≤
s
<
ℓ
‍
φ
(
N
r
)
.
Using the induction hypothesis for the second term on the right-hand side of (8) with an extra -
1 to take care of the case ℓ
=
1, we get
(9)
∑
N
r
∣
(
q
s
-
1
)
∀
s
∣
ℓ
,
1
≤
s
<
ℓ
‍
φ
(
N
r
)
=
∑
s
∣
ℓ
1
≤
s
<
ℓ
‍
(
∑
t
∣
s
‍
μ
(
t
)
q
s
/
t
)
-
1
=
∑
k
∣
ℓ
1
≤
k
<
ℓ
‍
q
k
∑
i
k
∣
ℓ
1
≤
i
k
<
ℓ
‍
μ
(
i
)
-
1
=
∑
k
∣
ℓ
1
≤
k
<
ℓ
‍
q
k
(
∑
i
∣
(
ℓ
/
k
)
‍
μ
(
i
)
-
μ
(
ℓ
k
)
)
-
1
=
-
∑
k
∣
ℓ
1
≤
k
<
ℓ
‍
q
k
μ
(
ℓ
k
)
-
1
=
-
∑
k
∣
ℓ
1
≤
k
<
ℓ
‍
μ
(
k
)
q
ℓ
/
k
-
1
.
The result now follows by substituting this into (8).Implicit in the proof of Theorem2 is the following nice identity.Corollary 3.
With the same notation as in Theorem2, one has
(10)
∑
1
≤
r
≤
d
o
N
r
(
q
)
=
ℓ
φ
(
N
r
)
=
∑
d
∣
ℓ
‍
μ
(
d
)
q
ℓ
/
d
-
⌊
1
ℓ
⌋
.


#### 2.1.2.  The CaseN
=
q
m
+
1

WhenN
=
q
m
+
1
(
m
∈
ℕ
), more precise information about q-cycles is now derived.Theorem 4.
Letm
∈
ℕ. Then (i)
o
q
m
+
1
(
q
)
=
2
m;
(ii)
2
m is the largest length among q-cycles(
q
m
+
1
) and any other length divides 2
m;
(iii)
the number ofq-cycles(
q
m
+
1
) having length ℓ is (
1
/
ℓ
)
∑
1
≤
r
≤
d
,
o
N
r
(
q
)
=
ℓ
‍
φ
(
N
r
).Proof.
Sinceq
2
m
≡
1 mod q
m
+
1, we have o
q
m
+
1
(
q
)
∣
2
m. Assertion (i) thus follows from the observation that o
q
m
+
1
(
q
)
>
m. Assertions (ii) and (iii) are direct consequences of Theorems 1(iii)–(vii).In [2], Yucas and Mullen introduced the following set:
(11)
D
m
:
=
{
(
q
k
)
{
-
1
}
n
∈
ℕ
;
n
∣
(
q
m
+
1
)
,
d
n
∤
(
q
k
+
1
)
,
k
∈
{
0,1
,
…
,
m
-
1
}
}
.
We show next that elements in this set can also be described through order.Lemma 5.
Letm, n
(
>
2
)
∈
ℕ. Then
n
∈
D
m
⇔ the  multiplicative  order  ofq
mod
⁡
n
is
2
m, that is, o
n
(
q
)
=
2
m, and  there  is  a positive integer t dividing m such  that n
∣
(
q
t
+
1
).Proof.
Ifn
∈
D
m, then n
∣
(
q
2
m
-
1
). If n
∣
(
q
s
-
1
)
(
s
∈
ℕ
), then [2, Proposition 1] tells us that s must be an even multiple of m. Thus, o
n
(
q
)
=
2
m. Conversely, assume that o
n
(
q
)
=
2
m and t is the least positive integer for which n
∣
(
q
t
+
1
). Thus, [2, Proposition 1] tells us that 2
m is an even multiple of t, and so t
∣
m. If t
<
m, the divisibility n
∣
(
q
2
t
-
1
) contradicts o
n
(
q
)
=
2
m. Hence, t
=
m.The next proposition, which is of independent interest, connects the sum in Theorem4(iii) with one involving the Möbius function.Proposition 6.
One has(12)
∑
n
∈
D
m
‍
φ
(
n
)
=
{
q
m
-
1
i
f
m
i
s
a
p
o
w
e
r
o
f
2
,
q
i
s
o
d
d
,
q
m
i
f
m
i
s
a
p
o
w
e
r
o
f
2
,
q
i
s
e
v
e
n
,
∑
i
∣
m
i
o
d
d
μ
(
i
)
q
m
/
i
i
f
m
i
s
n
o
t
a
p
o
w
e
r
o
f
2
.To prove Proposition6, we need some arithmetical facts about greatest common divisors.Lemma 7.
Lete
,
f
,
s
,
m
∈
ℕ. Then
(13)
gcd
⁡
(
q
e
+
1
,
q
f
-
1
)
=
{
1
,
i
f
gcd
(
2
e
,
f
)
=
gcd
(
e
,
f
)
,
2
∣
q
2
,
i
f
gcd
(
2
e
,
f
)
=
gcd
(
e
,
f
)
,
2
∤
q
q
gcd
(
e
,
f
)
+
1
,
i
f
gcd
(
2
e
,
f
)
=
2
gcd
(
e
,
f
)
,
(14)
gcd
⁡
(
q
s
+
1
,
q
m
+
1
)
=
{
1
,
i
f
ν
(
m
)
≥
ν
(
m
-
s
)
,
2
∣
q
2
,
i
f
ν
(
m
)
≥
ν
(
m
-
s
)
,
2
∤
q
q
gcd
(
m
,
s
)
+
1
,
i
f
ν
(
m
)
<
ν
(
m
-
s
)
,
where ν
(
j
)
=
ν
2
(
j
) denotes the highest power of 2 that divides j
∈
ℕ.Proof.
To prove (13), we consider two separate cases.
Case  1 (gcd
(
2
e
,
f
)
=
gcd
(
e
,
f
)). Observe that
(15)
gcd
⁡
(
q
e
+
1
,
q
f
-
1
)
∣
gcd
⁡
(
q
2
e
-
1
,
q
f
-
1
)
=
q
gcd
(
2
e
,
f
)
-
1
=
(
q
gcd
(
e
,
f
)
-
1
)
∣
(
q
e
-
1
)
.
If 2
∣
q, then gcd
(
q
e
+
1
,
q
e
-
1
)
=
1, and we infer that gcd
(
q
e
+
1
,
q
f
-
1
)
=
1.
If2
∤
q, then gcd
(
q
e
+
1
,
q
e
-
1
)
=
2, and we infer that gcd
(
q
e
+
1
,
q
f
-
1
)
=
2.
Case  2 (gcd
(
2
e
,
f
)
=
2
gcd
(
e
,
f
)). Observe that
(16)
gcd
⁡
(
q
e
+
1
,
q
f
-
1
)
∣
gcd
⁡
(
q
2
e
-
1
,
q
f
-
1
)
=
q
gcd
⁡
(
2
e
,
f
)
-
1
=
q
2
gcd
⁡
(
e
,
f
)
-
1
=
(
q
gcd
(
e
,
f
)
-
1
)
(
q
gcd
(
e
,
f
)
+
1
)
.
If 2
∣
q, then gcd
(
q
e
+
1
,
q
gcd
(
e
,
f
)
-
1
)
=
1, and from (16), we have
(17)
gcd
(
q
e
+
1
,
q
f
-
1
)
∣
(
q
gcd
(
e
,
f
)
+
1
)
.
On the other hand,
(18)
(
q
gcd
(
e
,
f
)
+
1
)
∣
(
q
2
gcd
(
e
,
f
)
-
1
)
=
(
q
gcd
(
2
e
,
f
)
-
1
)
∣
(
q
f
-
1
)
.
Since e
/
gcd
(
e
,
f
) is odd, we have (
q
gcd
(
e
,
f
)
+
1
)
∣
(
q
e
+
1
). This last relation together with (17) and (18) yields gcd
(
q
e
+
1
,
q
f
-
1
)
=
q
gcd
(
e
,
f
)
+
1, as required.
If2
∤
q, then gcd
(
(
q
e
+
1
)
/
2
,
(
q
gcd
(
e
,
f
)
-
1
)
/
2
)
=
1, and so we infer from (16) that
(19)
gcd
(
q
e
+
1
2
,
q
f
-
1
2
)
∣
(
q
gcd
(
e
,
f
)
+
1
)
.
Since (18) holds, we have
(20)
q
gcd
(
e
,
f
)
+
1
2
∣
q
f
-
1
2
.
Since e
/
gcd
(
e
,
f
) is odd, we also have
(21)
q
gcd
(
e
,
f
)
+
1
2
∣
q
e
+
1
2
.
The relations (20) and (21) show that
(22)
gcd
(
q
e
+
1
2
,
q
f
-
1
2
)
=
q
gcd
(
e
,
f
)
+
1
2
gcd
(
k
1
,
k
2
)
for some k
1, k
2
∈
ℕ. Taking (19) into account, we deduce that gcd
(
k
1
,
k
2
)
=
1 or 2. To complete the proof, it suffices to verify that gcd
(
k
1
,
k
2
)
=
1. To this end, suppose that gcd
(
k
1
,
k
2
)
=
2. Thus, (22) yields
(23)
2
(
q
gcd
(
e
,
f
)
+
1
)
∣
(
q
e
+
1
)
.
Since e
/
gcd
(
e
,
f
) is odd, we see that q
e
+
1
=
(
q
gcd
(
e
,
f
)
+
1
)
G, where G
∈
ℕ is odd. Combining this last relation with (23), we arrive that 2
∣
G, which is untenable.
To prove (14), we first observe that
(24)
gcd
(
2
e
,
f
)
=
gcd
(
e
,
f
)
⟺
ν
(
e
)
≥
ν
(
f
)
,
gcd
(
2
e
,
f
)
=
2
gcd
(
e
,
f
)
⟺
ν
(
e
)
<
ν
(
f
)
.
Putting m
=
e, m
-
s
=
f in (13), the desired result (14) follows at once if we can show that
(25)
gcd
(
q
m
+
1
,
q
m
-
s
-
1
)
=
gcd
(
q
m
+
1
,
q
s
+
1
)
.
To this end, let d
1
=
gcd
(
q
m
+
1
,
q
m
-
s
-
1
), d
2
=
gcd
(
q
m
+
1
,
q
s
+
1
). It is easily checked that d
1
=
d
2 because d
2
∣
d
1
⇔
d
2
∣
(
q
m
-
s
-
1
) and d
1
∣
d
2
⇔
d
1
∣
(
q
s
+
1
).We are now ready to prove Proposition6.Case 1 (m is a power of 2).
Clearly, in this caseν
(
m
)
≥
ν
(
m
-
s
) for 0
≤
s
<
m. For brevity, let
(26)
S
m
≔
{
n
∈
ℕ
;
n
∣
(
q
s
+
1
)
d
for
some
s
∈
{
0,1
,
…
,
m
-
1
}
,
n
∣
(
q
m
+
1
)
}
.
Thus, ∑
n
∈
D
m
‍
φ
(
n
)
=
∑
n
∣
(
q
m
+
1
)
‍
φ
(
n
)
-
∑
n
∈
S
m
‍
φ
(
n
). If 2
∣
q, then using (14), we see that those s
∈
{
0,1
,
…
,
m
-
1
} for which n
∣
(
q
s
+
1
) must satisfy gcd
(
q
s
+
1
,
q
m
+
1
)
=
1, showing that n
=
1. On the other hand, if 2
∤
q, then using (14), we see those s
∈
{
0,1
,
…
,
m
-
1
} for which n
∣
(
q
s
+
1
) must satisfy gcd
(
q
s
+
1
,
q
m
+
1
)
=
2, showing that n
=
1,2. Combining the two possibilities, we get
(27)
∑
n
∈
D
m
‍
φ
(
n
)
=
∑
n
∣
(
q
m
+
1
)
‍
φ
(
n
)
-
{
φ
(
1
)
,
if
2
∣
q
,
φ
(
1
)
+
φ
(
2
)
,
if
2
∤
q
,
=
{
q
m
,
if
2
∣
q
,
q
m
-
1
,
if
2
∤
q
.Case 2 (m is not a power of 2).
Thenm
=
2
ν
u, where ν
:
=
ν
(
m
) and u
(
≥
3
) is odd. From (14), we need to find those s
∈
{
0,1
,
…
,
m
-
1
} for which ν
(
m
-
s
)
>
ν
(
m
). These are s such that m
-
s
=
2
v
+
1
w
(
w
∈
ℕ
); that is, s
=
2
v
(
u
-
2
w
). Thus, all such s are of the form
(28)
s
=
2
ν
·
1
,
2
ν
·
3
,
…
,
2
ν
·
(
u
-
2
)
and correspondingly, gcd
(
s
,
m
)
=
2
ν
c, for some c
∣
u, 1
≤
c
<
u. We proceed now by induction on u, noting that the case u
=
1 (and u
=
2) is contained in Case 1. We have
(29)
∑
n
∈
D
m
‍
φ
(
n
)
=
∑
n
∣
(
q
m
+
1
)
‍
φ
(
n
)
-
∑
n
∈
S
m
‍
φ
(
n
)
=
q
m
+
1
-
∑
c
∣
u
1
≤
c
<
u
∑
n
∈
D
2
ν
c
‍
φ
(
n
)
+
{
φ
(
1
)
if
2
∣
q
φ
(
1
)
+
φ
(
2
)
if
2
∤
q
=
q
m
-
∑
c
∣
u
1
<
c
<
u
∑
i
∣
c
‍
μ
(
i
)
q
2
ν
c
/
i
-
{
0
+
q
2
ν
if
2
∣
q
1
+
q
2
ν
-
1
if
2
∤
q
dddddddddddddddddddddddd
(
using
induction
)
=
q
m
-
∑
c
∣
u
1
≤
c
<
u
∑
i
∣
c
‍
μ
(
i
)
q
2
ν
c
/
i
=
q
m
-
∑
k
∣
u
1
≤
k
<
u
q
2
ν
k
∑
i
∣
(
u
/
k
)
1
≤
i
<
u
/
k
μ
(
i
)
=
q
m
+
∑
k
∣
u
1
≤
k
<
u
q
2
ν
k
μ
(
u
k
)
=
∑
j
∣
m
j
odd
μ
(
j
)
q
m
/
j
.


## 2.1. Two Special Cases

There are two particular casesN
=
q
n
-
1 and N
=
q
m
+
1, which are closely related to primitive and self-reciprocal and will be needed in the last section.


### 2.1.1. The CaseN
=
q
n
-
1

WhenN
=
q
n
-
1
(
n
∈
ℕ
), more precise information is now derived.Theorem 2.
Letn
∈
ℕ. Then (i)
o
q
n
-
1
(
q
)
=
n;
(ii)
n is the largest length among q-cycles(
q
n
-
1
) and any other length of q-cycles(
q
n
-
1
) divides n;
(iii)
the number ofq-cycles(
q
n
-
1
) having length ℓ is equal to
(6)
1
ℓ
∑
1
≤
r
≤
d
o
N
r
(
q
)
=
ℓ
‍
φ
(
N
r
)
=
{
q
-
1
i
f
ℓ
=
1
1
ℓ
∑
k
∣
ℓ
‍
μ
(
k
)
q
ℓ
/
k
i
f
ℓ
>
1
.Proof.
Assertions (i) and (ii) are immediate from the definition and Theorems1(iii)-(iv). To verify (iii), observe that if ℓ
=
1, then it is easily checked that all the q-cycles(
q
n
-
1
) of length 1 are those starting with 0, A
:
=
q
n
-
1
+
q
n
-
2
+
⋯
+
q
+
1,2
A
,
…
,
(
q
-
2
)
A whose total number is q
-
1. Assume now that ℓ
>
1 and that the assertion holds up to ℓ
-
1. From Theorem 1(vii), the number of q-cycles(
q
n
-
1
) having length ℓ is (
1
/
ℓ
)
∑
1
≤
r
≤
d
,
o
N
r
(
q
)
=
ℓ
‍
φ
(
N
r
). Thus, to prove the desired result, we only need to verify that
(7)
∑
1
≤
r
≤
d
o
N
r
(
q
)
=
ℓ
‍
φ
(
N
r
)
=
∑
k
∣
ℓ
‍
μ
(
k
)
q
ℓ
/
k
.
Consider
(8)
∑
1
≤
r
≤
d
o
N
r
(
q
)
=
ℓ
‍
φ
(
N
r
)
=
∑
N
r
∣
(
q
ℓ
-
1
)
N
r
∤
(
q
s
-
1
)
∀
s
∣
ℓ
,
1
≤
s
<
ℓ
‍
φ
(
N
r
)
=
∑
N
r
∣
(
q
ℓ
-
1
)
‍
φ
(
N
r
)
-
∑
N
r
∣
(
q
s
-
1
)
∀
s
∣
ℓ
,
1
≤
s
<
ℓ
‍
φ
(
N
r
)
=
q
ℓ
-
1
-
∑
N
r
∣
(
q
s
-
1
)
∀
s
∣
ℓ
,
1
≤
s
<
ℓ
‍
φ
(
N
r
)
.
Using the induction hypothesis for the second term on the right-hand side of (8) with an extra -
1 to take care of the case ℓ
=
1, we get
(9)
∑
N
r
∣
(
q
s
-
1
)
∀
s
∣
ℓ
,
1
≤
s
<
ℓ
‍
φ
(
N
r
)
=
∑
s
∣
ℓ
1
≤
s
<
ℓ
‍
(
∑
t
∣
s
‍
μ
(
t
)
q
s
/
t
)
-
1
=
∑
k
∣
ℓ
1
≤
k
<
ℓ
‍
q
k
∑
i
k
∣
ℓ
1
≤
i
k
<
ℓ
‍
μ
(
i
)
-
1
=
∑
k
∣
ℓ
1
≤
k
<
ℓ
‍
q
k
(
∑
i
∣
(
ℓ
/
k
)
‍
μ
(
i
)
-
μ
(
ℓ
k
)
)
-
1
=
-
∑
k
∣
ℓ
1
≤
k
<
ℓ
‍
q
k
μ
(
ℓ
k
)
-
1
=
-
∑
k
∣
ℓ
1
≤
k
<
ℓ
‍
μ
(
k
)
q
ℓ
/
k
-
1
.
The result now follows by substituting this into (8).Implicit in the proof of Theorem2 is the following nice identity.Corollary 3.
With the same notation as in Theorem2, one has
(10)
∑
1
≤
r
≤
d
o
N
r
(
q
)
=
ℓ
φ
(
N
r
)
=
∑
d
∣
ℓ
‍
μ
(
d
)
q
ℓ
/
d
-
⌊
1
ℓ
⌋
.


### 2.1.2.  The CaseN
=
q
m
+
1

WhenN
=
q
m
+
1
(
m
∈
ℕ
), more precise information about q-cycles is now derived.Theorem 4.
Letm
∈
ℕ. Then (i)
o
q
m
+
1
(
q
)
=
2
m;
(ii)
2
m is the largest length among q-cycles(
q
m
+
1
) and any other length divides 2
m;
(iii)
the number ofq-cycles(
q
m
+
1
) having length ℓ is (
1
/
ℓ
)
∑
1
≤
r
≤
d
,
o
N
r
(
q
)
=
ℓ
‍
φ
(
N
r
).Proof.
Sinceq
2
m
≡
1 mod q
m
+
1, we have o
q
m
+
1
(
q
)
∣
2
m. Assertion (i) thus follows from the observation that o
q
m
+
1
(
q
)
>
m. Assertions (ii) and (iii) are direct consequences of Theorems 1(iii)–(vii).In [2], Yucas and Mullen introduced the following set:
(11)
D
m
:
=
{
(
q
k
)
{
-
1
}
n
∈
ℕ
;
n
∣
(
q
m
+
1
)
,
d
n
∤
(
q
k
+
1
)
,
k
∈
{
0,1
,
…
,
m
-
1
}
}
.
We show next that elements in this set can also be described through order.Lemma 5.
Letm, n
(
>
2
)
∈
ℕ. Then
n
∈
D
m
⇔ the  multiplicative  order  ofq
mod
⁡
n
is
2
m, that is, o
n
(
q
)
=
2
m, and  there  is  a positive integer t dividing m such  that n
∣
(
q
t
+
1
).Proof.
Ifn
∈
D
m, then n
∣
(
q
2
m
-
1
). If n
∣
(
q
s
-
1
)
(
s
∈
ℕ
), then [2, Proposition 1] tells us that s must be an even multiple of m. Thus, o
n
(
q
)
=
2
m. Conversely, assume that o
n
(
q
)
=
2
m and t is the least positive integer for which n
∣
(
q
t
+
1
). Thus, [2, Proposition 1] tells us that 2
m is an even multiple of t, and so t
∣
m. If t
<
m, the divisibility n
∣
(
q
2
t
-
1
) contradicts o
n
(
q
)
=
2
m. Hence, t
=
m.The next proposition, which is of independent interest, connects the sum in Theorem4(iii) with one involving the Möbius function.Proposition 6.
One has(12)
∑
n
∈
D
m
‍
φ
(
n
)
=
{
q
m
-
1
i
f
m
i
s
a
p
o
w
e
r
o
f
2
,
q
i
s
o
d
d
,
q
m
i
f
m
i
s
a
p
o
w
e
r
o
f
2
,
q
i
s
e
v
e
n
,
∑
i
∣
m
i
o
d
d
μ
(
i
)
q
m
/
i
i
f
m
i
s
n
o
t
a
p
o
w
e
r
o
f
2
.To prove Proposition6, we need some arithmetical facts about greatest common divisors.Lemma 7.
Lete
,
f
,
s
,
m
∈
ℕ. Then
(13)
gcd
⁡
(
q
e
+
1
,
q
f
-
1
)
=
{
1
,
i
f
gcd
(
2
e
,
f
)
=
gcd
(
e
,
f
)
,
2
∣
q
2
,
i
f
gcd
(
2
e
,
f
)
=
gcd
(
e
,
f
)
,
2
∤
q
q
gcd
(
e
,
f
)
+
1
,
i
f
gcd
(
2
e
,
f
)
=
2
gcd
(
e
,
f
)
,
(14)
gcd
⁡
(
q
s
+
1
,
q
m
+
1
)
=
{
1
,
i
f
ν
(
m
)
≥
ν
(
m
-
s
)
,
2
∣
q
2
,
i
f
ν
(
m
)
≥
ν
(
m
-
s
)
,
2
∤
q
q
gcd
(
m
,
s
)
+
1
,
i
f
ν
(
m
)
<
ν
(
m
-
s
)
,
where ν
(
j
)
=
ν
2
(
j
) denotes the highest power of 2 that divides j
∈
ℕ.Proof.
To prove (13), we consider two separate cases.
Case  1 (gcd
(
2
e
,
f
)
=
gcd
(
e
,
f
)). Observe that
(15)
gcd
⁡
(
q
e
+
1
,
q
f
-
1
)
∣
gcd
⁡
(
q
2
e
-
1
,
q
f
-
1
)
=
q
gcd
(
2
e
,
f
)
-
1
=
(
q
gcd
(
e
,
f
)
-
1
)
∣
(
q
e
-
1
)
.
If 2
∣
q, then gcd
(
q
e
+
1
,
q
e
-
1
)
=
1, and we infer that gcd
(
q
e
+
1
,
q
f
-
1
)
=
1.
If2
∤
q, then gcd
(
q
e
+
1
,
q
e
-
1
)
=
2, and we infer that gcd
(
q
e
+
1
,
q
f
-
1
)
=
2.
Case  2 (gcd
(
2
e
,
f
)
=
2
gcd
(
e
,
f
)). Observe that
(16)
gcd
⁡
(
q
e
+
1
,
q
f
-
1
)
∣
gcd
⁡
(
q
2
e
-
1
,
q
f
-
1
)
=
q
gcd
⁡
(
2
e
,
f
)
-
1
=
q
2
gcd
⁡
(
e
,
f
)
-
1
=
(
q
gcd
(
e
,
f
)
-
1
)
(
q
gcd
(
e
,
f
)
+
1
)
.
If 2
∣
q, then gcd
(
q
e
+
1
,
q
gcd
(
e
,
f
)
-
1
)
=
1, and from (16), we have
(17)
gcd
(
q
e
+
1
,
q
f
-
1
)
∣
(
q
gcd
(
e
,
f
)
+
1
)
.
On the other hand,
(18)
(
q
gcd
(
e
,
f
)
+
1
)
∣
(
q
2
gcd
(
e
,
f
)
-
1
)
=
(
q
gcd
(
2
e
,
f
)
-
1
)
∣
(
q
f
-
1
)
.
Since e
/
gcd
(
e
,
f
) is odd, we have (
q
gcd
(
e
,
f
)
+
1
)
∣
(
q
e
+
1
). This last relation together with (17) and (18) yields gcd
(
q
e
+
1
,
q
f
-
1
)
=
q
gcd
(
e
,
f
)
+
1, as required.
If2
∤
q, then gcd
(
(
q
e
+
1
)
/
2
,
(
q
gcd
(
e
,
f
)
-
1
)
/
2
)
=
1, and so we infer from (16) that
(19)
gcd
(
q
e
+
1
2
,
q
f
-
1
2
)
∣
(
q
gcd
(
e
,
f
)
+
1
)
.
Since (18) holds, we have
(20)
q
gcd
(
e
,
f
)
+
1
2
∣
q
f
-
1
2
.
Since e
/
gcd
(
e
,
f
) is odd, we also have
(21)
q
gcd
(
e
,
f
)
+
1
2
∣
q
e
+
1
2
.
The relations (20) and (21) show that
(22)
gcd
(
q
e
+
1
2
,
q
f
-
1
2
)
=
q
gcd
(
e
,
f
)
+
1
2
gcd
(
k
1
,
k
2
)
for some k
1, k
2
∈
ℕ. Taking (19) into account, we deduce that gcd
(
k
1
,
k
2
)
=
1 or 2. To complete the proof, it suffices to verify that gcd
(
k
1
,
k
2
)
=
1. To this end, suppose that gcd
(
k
1
,
k
2
)
=
2. Thus, (22) yields
(23)
2
(
q
gcd
(
e
,
f
)
+
1
)
∣
(
q
e
+
1
)
.
Since e
/
gcd
(
e
,
f
) is odd, we see that q
e
+
1
=
(
q
gcd
(
e
,
f
)
+
1
)
G, where G
∈
ℕ is odd. Combining this last relation with (23), we arrive that 2
∣
G, which is untenable.
To prove (14), we first observe that
(24)
gcd
(
2
e
,
f
)
=
gcd
(
e
,
f
)
⟺
ν
(
e
)
≥
ν
(
f
)
,
gcd
(
2
e
,
f
)
=
2
gcd
(
e
,
f
)
⟺
ν
(
e
)
<
ν
(
f
)
.
Putting m
=
e, m
-
s
=
f in (13), the desired result (14) follows at once if we can show that
(25)
gcd
(
q
m
+
1
,
q
m
-
s
-
1
)
=
gcd
(
q
m
+
1
,
q
s
+
1
)
.
To this end, let d
1
=
gcd
(
q
m
+
1
,
q
m
-
s
-
1
), d
2
=
gcd
(
q
m
+
1
,
q
s
+
1
). It is easily checked that d
1
=
d
2 because d
2
∣
d
1
⇔
d
2
∣
(
q
m
-
s
-
1
) and d
1
∣
d
2
⇔
d
1
∣
(
q
s
+
1
).We are now ready to prove Proposition6.Case 1 (m is a power of 2).
Clearly, in this caseν
(
m
)
≥
ν
(
m
-
s
) for 0
≤
s
<
m. For brevity, let
(26)
S
m
≔
{
n
∈
ℕ
;
n
∣
(
q
s
+
1
)
d
for
some
s
∈
{
0,1
,
…
,
m
-
1
}
,
n
∣
(
q
m
+
1
)
}
.
Thus, ∑
n
∈
D
m
‍
φ
(
n
)
=
∑
n
∣
(
q
m
+
1
)
‍
φ
(
n
)
-
∑
n
∈
S
m
‍
φ
(
n
). If 2
∣
q, then using (14), we see that those s
∈
{
0,1
,
…
,
m
-
1
} for which n
∣
(
q
s
+
1
) must satisfy gcd
(
q
s
+
1
,
q
m
+
1
)
=
1, showing that n
=
1. On the other hand, if 2
∤
q, then using (14), we see those s
∈
{
0,1
,
…
,
m
-
1
} for which n
∣
(
q
s
+
1
) must satisfy gcd
(
q
s
+
1
,
q
m
+
1
)
=
2, showing that n
=
1,2. Combining the two possibilities, we get
(27)
∑
n
∈
D
m
‍
φ
(
n
)
=
∑
n
∣
(
q
m
+
1
)
‍
φ
(
n
)
-
{
φ
(
1
)
,
if
2
∣
q
,
φ
(
1
)
+
φ
(
2
)
,
if
2
∤
q
,
=
{
q
m
,
if
2
∣
q
,
q
m
-
1
,
if
2
∤
q
.Case 2 (m is not a power of 2).
Thenm
=
2
ν
u, where ν
:
=
ν
(
m
) and u
(
≥
3
) is odd. From (14), we need to find those s
∈
{
0,1
,
…
,
m
-
1
} for which ν
(
m
-
s
)
>
ν
(
m
). These are s such that m
-
s
=
2
v
+
1
w
(
w
∈
ℕ
); that is, s
=
2
v
(
u
-
2
w
). Thus, all such s are of the form
(28)
s
=
2
ν
·
1
,
2
ν
·
3
,
…
,
2
ν
·
(
u
-
2
)
and correspondingly, gcd
(
s
,
m
)
=
2
ν
c, for some c
∣
u, 1
≤
c
<
u. We proceed now by induction on u, noting that the case u
=
1 (and u
=
2) is contained in Case 1. We have
(29)
∑
n
∈
D
m
‍
φ
(
n
)
=
∑
n
∣
(
q
m
+
1
)
‍
φ
(
n
)
-
∑
n
∈
S
m
‍
φ
(
n
)
=
q
m
+
1
-
∑
c
∣
u
1
≤
c
<
u
∑
n
∈
D
2
ν
c
‍
φ
(
n
)
+
{
φ
(
1
)
if
2
∣
q
φ
(
1
)
+
φ
(
2
)
if
2
∤
q
=
q
m
-
∑
c
∣
u
1
<
c
<
u
∑
i
∣
c
‍
μ
(
i
)
q
2
ν
c
/
i
-
{
0
+
q
2
ν
if
2
∣
q
1
+
q
2
ν
-
1
if
2
∤
q
dddddddddddddddddddddddd
(
using
induction
)
=
q
m
-
∑
c
∣
u
1
≤
c
<
u
∑
i
∣
c
‍
μ
(
i
)
q
2
ν
c
/
i
=
q
m
-
∑
k
∣
u
1
≤
k
<
u
q
2
ν
k
∑
i
∣
(
u
/
k
)
1
≤
i
<
u
/
k
μ
(
i
)
=
q
m
+
∑
k
∣
u
1
≤
k
<
u
q
2
ν
k
μ
(
u
k
)
=
∑
j
∣
m
j
odd
μ
(
j
)
q
m
/
j
.


## 2.1.1. The CaseN
=
q
n
-
1

WhenN
=
q
n
-
1
(
n
∈
ℕ
), more precise information is now derived.Theorem 2.
Letn
∈
ℕ. Then (i)
o
q
n
-
1
(
q
)
=
n;
(ii)
n is the largest length among q-cycles(
q
n
-
1
) and any other length of q-cycles(
q
n
-
1
) divides n;
(iii)
the number ofq-cycles(
q
n
-
1
) having length ℓ is equal to
(6)
1
ℓ
∑
1
≤
r
≤
d
o
N
r
(
q
)
=
ℓ
‍
φ
(
N
r
)
=
{
q
-
1
i
f
ℓ
=
1
1
ℓ
∑
k
∣
ℓ
‍
μ
(
k
)
q
ℓ
/
k
i
f
ℓ
>
1
.Proof.
Assertions (i) and (ii) are immediate from the definition and Theorems1(iii)-(iv). To verify (iii), observe that if ℓ
=
1, then it is easily checked that all the q-cycles(
q
n
-
1
) of length 1 are those starting with 0, A
:
=
q
n
-
1
+
q
n
-
2
+
⋯
+
q
+
1,2
A
,
…
,
(
q
-
2
)
A whose total number is q
-
1. Assume now that ℓ
>
1 and that the assertion holds up to ℓ
-
1. From Theorem 1(vii), the number of q-cycles(
q
n
-
1
) having length ℓ is (
1
/
ℓ
)
∑
1
≤
r
≤
d
,
o
N
r
(
q
)
=
ℓ
‍
φ
(
N
r
). Thus, to prove the desired result, we only need to verify that
(7)
∑
1
≤
r
≤
d
o
N
r
(
q
)
=
ℓ
‍
φ
(
N
r
)
=
∑
k
∣
ℓ
‍
μ
(
k
)
q
ℓ
/
k
.
Consider
(8)
∑
1
≤
r
≤
d
o
N
r
(
q
)
=
ℓ
‍
φ
(
N
r
)
=
∑
N
r
∣
(
q
ℓ
-
1
)
N
r
∤
(
q
s
-
1
)
∀
s
∣
ℓ
,
1
≤
s
<
ℓ
‍
φ
(
N
r
)
=
∑
N
r
∣
(
q
ℓ
-
1
)
‍
φ
(
N
r
)
-
∑
N
r
∣
(
q
s
-
1
)
∀
s
∣
ℓ
,
1
≤
s
<
ℓ
‍
φ
(
N
r
)
=
q
ℓ
-
1
-
∑
N
r
∣
(
q
s
-
1
)
∀
s
∣
ℓ
,
1
≤
s
<
ℓ
‍
φ
(
N
r
)
.
Using the induction hypothesis for the second term on the right-hand side of (8) with an extra -
1 to take care of the case ℓ
=
1, we get
(9)
∑
N
r
∣
(
q
s
-
1
)
∀
s
∣
ℓ
,
1
≤
s
<
ℓ
‍
φ
(
N
r
)
=
∑
s
∣
ℓ
1
≤
s
<
ℓ
‍
(
∑
t
∣
s
‍
μ
(
t
)
q
s
/
t
)
-
1
=
∑
k
∣
ℓ
1
≤
k
<
ℓ
‍
q
k
∑
i
k
∣
ℓ
1
≤
i
k
<
ℓ
‍
μ
(
i
)
-
1
=
∑
k
∣
ℓ
1
≤
k
<
ℓ
‍
q
k
(
∑
i
∣
(
ℓ
/
k
)
‍
μ
(
i
)
-
μ
(
ℓ
k
)
)
-
1
=
-
∑
k
∣
ℓ
1
≤
k
<
ℓ
‍
q
k
μ
(
ℓ
k
)
-
1
=
-
∑
k
∣
ℓ
1
≤
k
<
ℓ
‍
μ
(
k
)
q
ℓ
/
k
-
1
.
The result now follows by substituting this into (8).Implicit in the proof of Theorem2 is the following nice identity.Corollary 3.
With the same notation as in Theorem2, one has
(10)
∑
1
≤
r
≤
d
o
N
r
(
q
)
=
ℓ
φ
(
N
r
)
=
∑
d
∣
ℓ
‍
μ
(
d
)
q
ℓ
/
d
-
⌊
1
ℓ
⌋
.


## 2.1.2.  The CaseN
=
q
m
+
1

WhenN
=
q
m
+
1
(
m
∈
ℕ
), more precise information about q-cycles is now derived.Theorem 4.
Letm
∈
ℕ. Then (i)
o
q
m
+
1
(
q
)
=
2
m;
(ii)
2
m is the largest length among q-cycles(
q
m
+
1
) and any other length divides 2
m;
(iii)
the number ofq-cycles(
q
m
+
1
) having length ℓ is (
1
/
ℓ
)
∑
1
≤
r
≤
d
,
o
N
r
(
q
)
=
ℓ
‍
φ
(
N
r
).Proof.
Sinceq
2
m
≡
1 mod q
m
+
1, we have o
q
m
+
1
(
q
)
∣
2
m. Assertion (i) thus follows from the observation that o
q
m
+
1
(
q
)
>
m. Assertions (ii) and (iii) are direct consequences of Theorems 1(iii)–(vii).In [2], Yucas and Mullen introduced the following set:
(11)
D
m
:
=
{
(
q
k
)
{
-
1
}
n
∈
ℕ
;
n
∣
(
q
m
+
1
)
,
d
n
∤
(
q
k
+
1
)
,
k
∈
{
0,1
,
…
,
m
-
1
}
}
.
We show next that elements in this set can also be described through order.Lemma 5.
Letm, n
(
>
2
)
∈
ℕ. Then
n
∈
D
m
⇔ the  multiplicative  order  ofq
mod
⁡
n
is
2
m, that is, o
n
(
q
)
=
2
m, and  there  is  a positive integer t dividing m such  that n
∣
(
q
t
+
1
).Proof.
Ifn
∈
D
m, then n
∣
(
q
2
m
-
1
). If n
∣
(
q
s
-
1
)
(
s
∈
ℕ
), then [2, Proposition 1] tells us that s must be an even multiple of m. Thus, o
n
(
q
)
=
2
m. Conversely, assume that o
n
(
q
)
=
2
m and t is the least positive integer for which n
∣
(
q
t
+
1
). Thus, [2, Proposition 1] tells us that 2
m is an even multiple of t, and so t
∣
m. If t
<
m, the divisibility n
∣
(
q
2
t
-
1
) contradicts o
n
(
q
)
=
2
m. Hence, t
=
m.The next proposition, which is of independent interest, connects the sum in Theorem4(iii) with one involving the Möbius function.Proposition 6.
One has(12)
∑
n
∈
D
m
‍
φ
(
n
)
=
{
q
m
-
1
i
f
m
i
s
a
p
o
w
e
r
o
f
2
,
q
i
s
o
d
d
,
q
m
i
f
m
i
s
a
p
o
w
e
r
o
f
2
,
q
i
s
e
v
e
n
,
∑
i
∣
m
i
o
d
d
μ
(
i
)
q
m
/
i
i
f
m
i
s
n
o
t
a
p
o
w
e
r
o
f
2
.To prove Proposition6, we need some arithmetical facts about greatest common divisors.Lemma 7.
Lete
,
f
,
s
,
m
∈
ℕ. Then
(13)
gcd
⁡
(
q
e
+
1
,
q
f
-
1
)
=
{
1
,
i
f
gcd
(
2
e
,
f
)
=
gcd
(
e
,
f
)
,
2
∣
q
2
,
i
f
gcd
(
2
e
,
f
)
=
gcd
(
e
,
f
)
,
2
∤
q
q
gcd
(
e
,
f
)
+
1
,
i
f
gcd
(
2
e
,
f
)
=
2
gcd
(
e
,
f
)
,
(14)
gcd
⁡
(
q
s
+
1
,
q
m
+
1
)
=
{
1
,
i
f
ν
(
m
)
≥
ν
(
m
-
s
)
,
2
∣
q
2
,
i
f
ν
(
m
)
≥
ν
(
m
-
s
)
,
2
∤
q
q
gcd
(
m
,
s
)
+
1
,
i
f
ν
(
m
)
<
ν
(
m
-
s
)
,
where ν
(
j
)
=
ν
2
(
j
) denotes the highest power of 2 that divides j
∈
ℕ.Proof.
To prove (13), we consider two separate cases.
Case  1 (gcd
(
2
e
,
f
)
=
gcd
(
e
,
f
)). Observe that
(15)
gcd
⁡
(
q
e
+
1
,
q
f
-
1
)
∣
gcd
⁡
(
q
2
e
-
1
,
q
f
-
1
)
=
q
gcd
(
2
e
,
f
)
-
1
=
(
q
gcd
(
e
,
f
)
-
1
)
∣
(
q
e
-
1
)
.
If 2
∣
q, then gcd
(
q
e
+
1
,
q
e
-
1
)
=
1, and we infer that gcd
(
q
e
+
1
,
q
f
-
1
)
=
1.
If2
∤
q, then gcd
(
q
e
+
1
,
q
e
-
1
)
=
2, and we infer that gcd
(
q
e
+
1
,
q
f
-
1
)
=
2.
Case  2 (gcd
(
2
e
,
f
)
=
2
gcd
(
e
,
f
)). Observe that
(16)
gcd
⁡
(
q
e
+
1
,
q
f
-
1
)
∣
gcd
⁡
(
q
2
e
-
1
,
q
f
-
1
)
=
q
gcd
⁡
(
2
e
,
f
)
-
1
=
q
2
gcd
⁡
(
e
,
f
)
-
1
=
(
q
gcd
(
e
,
f
)
-
1
)
(
q
gcd
(
e
,
f
)
+
1
)
.
If 2
∣
q, then gcd
(
q
e
+
1
,
q
gcd
(
e
,
f
)
-
1
)
=
1, and from (16), we have
(17)
gcd
(
q
e
+
1
,
q
f
-
1
)
∣
(
q
gcd
(
e
,
f
)
+
1
)
.
On the other hand,
(18)
(
q
gcd
(
e
,
f
)
+
1
)
∣
(
q
2
gcd
(
e
,
f
)
-
1
)
=
(
q
gcd
(
2
e
,
f
)
-
1
)
∣
(
q
f
-
1
)
.
Since e
/
gcd
(
e
,
f
) is odd, we have (
q
gcd
(
e
,
f
)
+
1
)
∣
(
q
e
+
1
). This last relation together with (17) and (18) yields gcd
(
q
e
+
1
,
q
f
-
1
)
=
q
gcd
(
e
,
f
)
+
1, as required.
If2
∤
q, then gcd
(
(
q
e
+
1
)
/
2
,
(
q
gcd
(
e
,
f
)
-
1
)
/
2
)
=
1, and so we infer from (16) that
(19)
gcd
(
q
e
+
1
2
,
q
f
-
1
2
)
∣
(
q
gcd
(
e
,
f
)
+
1
)
.
Since (18) holds, we have
(20)
q
gcd
(
e
,
f
)
+
1
2
∣
q
f
-
1
2
.
Since e
/
gcd
(
e
,
f
) is odd, we also have
(21)
q
gcd
(
e
,
f
)
+
1
2
∣
q
e
+
1
2
.
The relations (20) and (21) show that
(22)
gcd
(
q
e
+
1
2
,
q
f
-
1
2
)
=
q
gcd
(
e
,
f
)
+
1
2
gcd
(
k
1
,
k
2
)
for some k
1, k
2
∈
ℕ. Taking (19) into account, we deduce that gcd
(
k
1
,
k
2
)
=
1 or 2. To complete the proof, it suffices to verify that gcd
(
k
1
,
k
2
)
=
1. To this end, suppose that gcd
(
k
1
,
k
2
)
=
2. Thus, (22) yields
(23)
2
(
q
gcd
(
e
,
f
)
+
1
)
∣
(
q
e
+
1
)
.
Since e
/
gcd
(
e
,
f
) is odd, we see that q
e
+
1
=
(
q
gcd
(
e
,
f
)
+
1
)
G, where G
∈
ℕ is odd. Combining this last relation with (23), we arrive that 2
∣
G, which is untenable.
To prove (14), we first observe that
(24)
gcd
(
2
e
,
f
)
=
gcd
(
e
,
f
)
⟺
ν
(
e
)
≥
ν
(
f
)
,
gcd
(
2
e
,
f
)
=
2
gcd
(
e
,
f
)
⟺
ν
(
e
)
<
ν
(
f
)
.
Putting m
=
e, m
-
s
=
f in (13), the desired result (14) follows at once if we can show that
(25)
gcd
(
q
m
+
1
,
q
m
-
s
-
1
)
=
gcd
(
q
m
+
1
,
q
s
+
1
)
.
To this end, let d
1
=
gcd
(
q
m
+
1
,
q
m
-
s
-
1
), d
2
=
gcd
(
q
m
+
1
,
q
s
+
1
). It is easily checked that d
1
=
d
2 because d
2
∣
d
1
⇔
d
2
∣
(
q
m
-
s
-
1
) and d
1
∣
d
2
⇔
d
1
∣
(
q
s
+
1
).We are now ready to prove Proposition6.Case 1 (m is a power of 2).
Clearly, in this caseν
(
m
)
≥
ν
(
m
-
s
) for 0
≤
s
<
m. For brevity, let
(26)
S
m
≔
{
n
∈
ℕ
;
n
∣
(
q
s
+
1
)
d
for
some
s
∈
{
0,1
,
…
,
m
-
1
}
,
n
∣
(
q
m
+
1
)
}
.
Thus, ∑
n
∈
D
m
‍
φ
(
n
)
=
∑
n
∣
(
q
m
+
1
)
‍
φ
(
n
)
-
∑
n
∈
S
m
‍
φ
(
n
). If 2
∣
q, then using (14), we see that those s
∈
{
0,1
,
…
,
m
-
1
} for which n
∣
(
q
s
+
1
) must satisfy gcd
(
q
s
+
1
,
q
m
+
1
)
=
1, showing that n
=
1. On the other hand, if 2
∤
q, then using (14), we see those s
∈
{
0,1
,
…
,
m
-
1
} for which n
∣
(
q
s
+
1
) must satisfy gcd
(
q
s
+
1
,
q
m
+
1
)
=
2, showing that n
=
1,2. Combining the two possibilities, we get
(27)
∑
n
∈
D
m
‍
φ
(
n
)
=
∑
n
∣
(
q
m
+
1
)
‍
φ
(
n
)
-
{
φ
(
1
)
,
if
2
∣
q
,
φ
(
1
)
+
φ
(
2
)
,
if
2
∤
q
,
=
{
q
m
,
if
2
∣
q
,
q
m
-
1
,
if
2
∤
q
.Case 2 (m is not a power of 2).
Thenm
=
2
ν
u, where ν
:
=
ν
(
m
) and u
(
≥
3
) is odd. From (14), we need to find those s
∈
{
0,1
,
…
,
m
-
1
} for which ν
(
m
-
s
)
>
ν
(
m
). These are s such that m
-
s
=
2
v
+
1
w
(
w
∈
ℕ
); that is, s
=
2
v
(
u
-
2
w
). Thus, all such s are of the form
(28)
s
=
2
ν
·
1
,
2
ν
·
3
,
…
,
2
ν
·
(
u
-
2
)
and correspondingly, gcd
(
s
,
m
)
=
2
ν
c, for some c
∣
u, 1
≤
c
<
u. We proceed now by induction on u, noting that the case u
=
1 (and u
=
2) is contained in Case 1. We have
(29)
∑
n
∈
D
m
‍
φ
(
n
)
=
∑
n
∣
(
q
m
+
1
)
‍
φ
(
n
)
-
∑
n
∈
S
m
‍
φ
(
n
)
=
q
m
+
1
-
∑
c
∣
u
1
≤
c
<
u
∑
n
∈
D
2
ν
c
‍
φ
(
n
)
+
{
φ
(
1
)
if
2
∣
q
φ
(
1
)
+
φ
(
2
)
if
2
∤
q
=
q
m
-
∑
c
∣
u
1
<
c
<
u
∑
i
∣
c
‍
μ
(
i
)
q
2
ν
c
/
i
-
{
0
+
q
2
ν
if
2
∣
q
1
+
q
2
ν
-
1
if
2
∤
q
dddddddddddddddddddddddd
(
using
induction
)
=
q
m
-
∑
c
∣
u
1
≤
c
<
u
∑
i
∣
c
‍
μ
(
i
)
q
2
ν
c
/
i
=
q
m
-
∑
k
∣
u
1
≤
k
<
u
q
2
ν
k
∑
i
∣
(
u
/
k
)
1
≤
i
<
u
/
k
μ
(
i
)
=
q
m
+
∑
k
∣
u
1
≤
k
<
u
q
2
ν
k
μ
(
u
k
)
=
∑
j
∣
m
j
odd
μ
(
j
)
q
m
/
j
.


## 3.  Order of a Polynomial

Following [3, page 84], for f
(
x
)
∈
𝔽
q
[
x
]
∖
{
0
} with f
(
0
)
≠
0, the least e
∈
ℕ for which f
(
x
) divides x
e
-
1 is called the order of f
(
x
), denoted by ord(
f
). If f
(
0
)
=
0, then f
(
x
)
=
x
h
g
(
x
), where h
∈
ℕ and g
∈
𝔽
q
[
x
] with g
(
0
)
≠
0 are uniquely determined, and ord(
f
) is defined to be ord(
g
). The order of a polynomial is also called the period or the exponent of that polynomial. The following facts are well-known.(i)
(see [3, Theorem 3.3]) Let f
(
x
)
∈
𝔽
q
[
x
] be irreducible with deg
⁡
(
f
)
=
m
∈
ℕ, f
(
0
)
≠
0. Then ord(
f
) is equal to the order of any root of f in the multiplicative group 𝔽
q
m
*.
(ii)
(see [3, Lemma 3.6]) Let c
∈
ℕ. Then f
∈
𝔽
q
[
x
] with f
(
0
)
≠
0 divides x
c
-
1 if and only if ord(
f
)
∣
c.
(iii)
(see [3, Theorem 3.8]) Let g
∈
𝔽
q
[
x
] be irreducible over 𝔽
q with g
(
0
)
≠
0 and ord(
g
)
=
e, and let f
=
g
b with b
∈
ℕ. Let t be the smallest integer with p
t
≥
b, where p is the characteristic of 𝔽
q. Then ord(
f
)
=
e
p
t.
(iv)
(see [3, Theorem 3.9]) Let g
1
,
…
,
g
k be pairwise relatively prime nonzero polynomials over 𝔽
q, and let f
=
g
1
⋯
g
k. Then ord(
f
)
=
lcm
{
ord
(
g
1
)
,
…
,
ord
(
g
k
)
}.


### 3.1. Counting Formulae

Working withq-cycles, apart from the known result, [3, Theorem 3.5], that the number of monic irreducible f
∈
𝔽
q
[
x
], f
(
0
)
≠
0 for which ord(
f
)
=
N
r
(
r
∈
{
1
,
…
,
d
}
) and deg
⁡
(
f
)
=
o
N
r
(
q
) is φ
(
N
r
)
/
o
N
r
(
q
), some new information about the number of monic irreducible polynomials is now derived.Theorem 8.
(i) The polynomialf
∈
𝔽
q
[
x
] constructed via (2) from a q
(
a
)-cycle(
N
) with gcd
(
a
,
N
)
=
N
r
(
r
∈
{
1
,
…
,
d
}
) is a monic irreducible polynomial with f
(
0
)
≠
0,  ord
(
f
)
=
N
/
N
r and deg
⁡
(
f
)
=
o
N
/
N
r
(
q
). Conversely, each irreducible polynomial f
∈
𝔽
q
[
x
] with f
(
0
)
≠
0, ord
(
f
)
=
N
r and deg
⁡
(
f
)
=
o
N
r
(
q
) is an irreducible factor of x
N
-
1 arisen, through (2), from an q
(
a
)-cycle(
N
) with gcd
(
a
,
N
)
=
N
/
N
r.
(ii) The set of monic, irreduciblef
∈
𝔽
q
[
x
], f
(
0
)
≠
0 for which ord
(
f
)
∣
N is identical with the set of irreducible factors of x
N
-
1.
(iii) The number ofq-cycles(
N
), the number of monic irreducible factors of x
N
-
1, and the number of monic irreducible f
∈
𝔽
q
[
x
] with f
(
0
)
≠
0 and ord
(
f
)
∣
N are all equal to ∑
r
=
1
d
‍
φ
(
N
r
)
/
o
N
r
(
q
).Proof.
From Theorem1(v), each q
(
a
)-cycle(
N
) with gcd
(
a
,
N
)
=
N
r has length o
N
/
N
r
(
q
) and it thus gives rise, through the α-correspondence, to a monic irreducible f
∈
𝔽
q
[
x
], f
(
0
)
≠
0, of degree o
N
/
N
r
(
q
). Each root of f is of the form α
a
q
i
(
i
∈
{
0,1
,
…
,
o
N
/
N
r
(
q
)
-
1
}
) where α is a primitive Nth root of unity, and so its order is N
/
N
r. Part (i) is thus a consequence of [3, Theorem 3.3] and the α-correspondence.
To prove (ii), note that if the monic irreduciblef
∈
𝔽
q
[
x
] satisfies f
(
0
)
≠
0 and ord(
f
)
∣
N, then ord(
f
)
=
N
r for some r
∈
{
1
,
…
,
d
}. Thus, f
∣
(
x
N
r
-
1
), and so f
∣
(
x
N
-
1
). On the other hand, if f is an irreducible factor of x
N
-
1, the α-correspondence assures us that f is constructed from a q-cycle(
N
) and the desired conclusion follows from (i).
Part (iii) follows (ii), theα-correspondence, and Theorem 1(viii).There is another straightforward technique to derive a formula for the number of monic irreducible polynomials of fixed order usingq-cycles based on the inclusion-exclusion principle. Although the formula so obtained is not easy to use, we give a proof to illustrate this different approach. For r
∈
{
1,2
,
…
,
d
}, set (keeping the earlier notation in the first section)
(30)
ℐ
N
r
=
{
monic
irreducible
polynomials
arising
from
d
the
q
-cycles
(
N
r
)
as
constructed
in
(
2
)
}
,
𝒪
N
d
=
𝒪
1
=
|
𝒞
1
|
,
𝒪
N
r
=
|
𝒞
N
r
|
-
∑
M
∣
N
r
,
M
<
N
r
‍
𝒪
M
.
For a given s
∈
ℕ and distinct primes p
1
,
p
2
,
…
,
p
k, define
(31)
〈
s
〉
≔
{
p
1
n
1
p
2
n
2
⋯
p
k
n
k
;
n
1
,
n
2
,
…
,
n
k
∈
ℕ
,
d
n
1
+
n
2
+
⋯
+
n
k
=
s
}
.Proposition 9.
LetN
=
p
1
n
1
p
2
n
2
⋯
p
k
n
k, the unique prime factorization of N. The number of monic, irreducible polynomials f
∈
𝔽
q
[
x
]
∖
𝔽
q, f
(
0
)
≠
0 having order N is equal to
(32)
𝒪
N
=
|
ℐ
N
1
|
-
|
⋃
r
=
2
d
ℐ
N
r
|
(33)
=
|
𝒞
N
1
|
-
{
∑
r
=
2
d
‍
|
𝒞
N
r
|
ssssss
-
∑
x
1
,
x
2
∈
{
N
2
,
N
3
,
…
,
N
d
}
,
x
1
<
x
2
‍
|
𝒞
gcd
⁡
(
x
1
,
x
2
)
|
ssssss
+
⋯
+
(
-
1
)
d
ssssss
×
∑
x
1
,
x
2
,
…
,
x
d
-
1
∈
{
N
2
,
N
3
,
…
,
N
d
}
,
x
1
<
x
2
<
⋯
<
x
d
-
1
‍
|
𝒞
gcd
⁡
(
x
1
,
x
2
,
…
,
x
d
-
1
)
|
∑
r
=
2
d
‍
}
(34)
=
|
𝒞
N
1
|
-
∑
m
∈
〈
s
-
1
〉
‍
|
𝒞
m
|
+
∑
m
∈
〈
s
-
2
〉
‍
|
𝒞
m
|
+
⋯
+
(
-
1
)
k
∑
m
∈
〈
s
-
k
〉
‍
|
𝒞
m
|
.Proof.
Since the number of distinct irreducible factors ofx
N
-
1 in 𝔽
q
[
x
] is equal to the number of q-cycles(
N
) [1, Corollary 9.12], from its definition, the α-correspondence and [3, Lemma 3.6], 𝒪
N
r is simply the number irreducible factors (in 𝔽
q
[
x
] constructed through (2)) of x
N
r
-
1 which are not irreducible factors of x
M
-
1 for any M
∣
N
r, M
<
N
r, which is in turn equivalent to saying that 𝒪
N
r is the number of monic, irreducible polynomials f
∈
𝔽
q
[
x
], f
(
0
)
≠
0, having order N
r, and this proves (32).
Again using [1, Corollary 9.12] and [3, Lemma 3.6] to translate the number of q-cycles to those of corresponding irreducible polynomials, the inclusion-exclusion formulae on the right-hand sides of (33) and (34) clearly yield the number of irreducible factors of x
N
-
1 which are not irreducible factors of x
N
r
-
1 for all r
∈
{
2,3
,
…
,
d
}, and this verifies (33) and (34).Remark 10.
Let us remark that there are no irreducible polynomials in𝔽
q
[
x
] of order n with gcd
(
q
,
n
)
>
1. This is seen as follows: for f
(
x
)
∈
𝔽
q
[
x
] with f
(
0
)
≠
0, since ord(
f
) is the least positive integer for which f
(
x
) divides x
ord
(
f
)
-
1, monic irreducible polynomials of order n are contained in the set of irreducible factors of x
n
-
1 in 𝔽
q
[
x
]. Putting n
=
N
p
e
(
e
∈
ℕ
,
gcd
(
q
,
N
)
=
1
), since x
n
-
1
=
(
x
N
-
1
)
p
e, the set of all irreducible factors of x
n
-
1 is identical with the set of all irreducible factors of x
N
-
1, and so each irreducible factor of x
n
-
1 is of order ≤
N
<
n.In contrast to the preceding remark, there always exists a (reducible) polynomial in𝔽
q
[
x
] of order n with gcd
(
q
,
n
)
>
1. This is seen as follows: using the terminology of the last remark, since gcd
(
q
,
N
)
=
1, Theorem 8 assures us that there always exists a monic, irreducible polynomial g
(
x
)
∈
𝔽
q
[
x
], g
(
0
)
≠
0, having ord
(
g
)
=
N. Consequently, Theorem 3.8 in [3] tells us that ord(
g
(
x
)
p
e
)
=
N
p
e
=
n.Our next task is to compute the number of monic polynomials in𝔽
q
[
x
] (both reducible and irreducible) having order N. Let f
(
x
)
∈
𝔽
q
[
x
] be a factor of the polynomial x
N
-
1 with ord(
f
)
=
N. Since gcd
(
q
,
N
)
=
1, the polynomial x
N
-
1 has no multiple factors. Assume that f
(
x
) is decomposed into k distinct monic irreducible factors (in 𝔽
q
[
x
]), say, f
(
x
)
=
f
1
(
x
)
⋯
f
k
(
x
). Since ord
(
f
)
=
N
=
lcm
{
ord
(
f
1
)
,
…
,
ord
(
f
k
)
}, each ord(
f
i
)
∈
{
N
=
N
1
>
N
2
>
⋯
>
N
d
=
1
} (the set of all divisors of N). Thus, the number of all such f's is equal to ∑
e
1
+
e
2
+
⋯
+
e
d
=
k
,
e
r
≥
0
,
lcm
(
N
r
;
e
r
≠
0
)
=
N
(
𝒪
N
1
e
1
)
⋯
(
𝒪
N
d
e
d
). We have thus proved.Theorem 11.
The total number of monic polynomials (both reducible and irreducible)f
∈
𝔽
q
[
x
], f
(
0
)
≠
0, having order N is
(35)
∑
k
=
1
m
‍
∑
e
1
+
e
2
+
⋯
+
e
d
=
k
,
e
r
≥
0
lcm
(
N
r
;
e
r
≠
0
)
=
N
‍
(
𝒪
N
1
e
1
)
⋯
(
𝒪
N
d
e
d
)
,
m
:
=
∑
r
=
1
d
‍
𝒪
N
r
.Having determined the number of polynomials with fixed order, it is natural to find out how many of them have orders dividing a fixedn
∈
ℕ.Theorem 12.
Letn
=
p
e
N
∈
ℕ with e
∈
ℕ
0 and gcd
(
q
,
N
)
=
1. Then the product of all monic irreducible polynomials f
∈
𝔽
q
[
x
], f
(
0
)
≠
0 for which ord
(
f
)
∣
n is equal to x
N
-
1 and their number is equal to |
𝒞
N
|
=
∑
r
=
1
d
‍
φ
(
N
r
)
/
o
N
r
(
q
).Proof.
Sincex
n
-
1
=
(
x
N
-
1
)
p
e, the set of all monic irreducible factors of x
N
-
1 is identical with the set of all monic irreducible factors of x
n
-
1. From [3, Theorem 3.6], for f
∈
𝔽
q
[
x
], f
(
0
)
≠
0, we know that ord(
f
)
∣
n if and only if f
(
x
)
∣
(
x
n
-
1
). Thus, the set of all monic irreducible polynomials f
∈
𝔽
q
[
x
], f
(
0
)
≠
0 for which ord(
f
)
∣
n is identical with the set of all irreducible factors of x
n
-
1 which is also equal to the set of all irreducible factors of x
N
-
1. Since x
N
-
1 has no multiple root, the product of all monic irreducible polynomials f
∈
𝔽
q
[
x
], f
(
0
)
≠
0 for which ord(
f
)
∣
n is x
N
-
1 and the first assertion is established. The second assertion follows immediately from the first assertion and Theorem 8(iv).


### 3.2. Some Explicit Shapes

Having counted the number of monic irreducible polynomials of fixed order, we proceed to determine their explicit shapes. From [1, Corollary 9.12], we know that the number of irreducible factors of x
N
-
1 in 𝔽
q
[
x
] is equal to the number of q-cycles(
N
) formed by the N numbers 0,1
,
…
,
N
-
1. To determine explicit shapes of all monic, irreducible polynomials f
∈
𝔽
q
[
x
], f
(
0
)
≠
0, having order N, we consider the polynomial
(36)
f
(
x
)
=
(
x
-
α
a
0
)
(
x
-
α
a
1
)
⋯
(
x
-
α
a
ℓ
-
1
)
∈
𝔽
q
[
x
]
associated with the q-cycle(
N
)
(
a
0
,
a
1
,
…
,
a
ℓ
-
1
), where α is a primitive Nth root of unity. By definition, [3, Lemma 3.6] and [1, Theorem 9.11], among all such polynomials, those which do not divide x
N
r
-
1, r
∈
{
2,3
,
…
,
d
}, are all the sought after polynomials having order N.Although, the procedure just described is satisfactory in principle, in certain cases, more precise shapes can be given. For a positive integern not divisible by p, recall that the nth cyclotomic polynomial [3, page 64] is defined as
(37)
Q
n
(
x
)
=
∏
i
=
1
gcd
(
i
,
n
)
=
1
n
(
x
-
ζ
i
)
=
∏
i
∣
n
‍
(
x
i
-
1
)
μ
(
n
/
i
)
∈
𝔽
q
[
x
]
,
where ζ is a primitive nth root of unity and μ is the Möbius function. It is known that
(38)
x
N
-
1
=
∏
r
=
1
d
‍
Q
N
r
(
x
)
.Proposition 13.
Letd
=
d
(
N
) be the number of divisors of N. (i)
If the number ofq-cycles(
N
) is equal to d, then in (38) each Q
N
r
(
x
) is irreducible in 𝔽
q
[
x
] and ord
(
Q
N
r
)
=
N
r. In particular, Q
N
(
x
)
∈
𝔽
q
[
x
] is irreducible and of order N. The same conclusion holds if q is a primitive root mod N
r for all r
∈
{
1,2
,
…
,
d
}.
(ii)
IfQ
N
r
(
x
) is irreducible in 𝔽
q
[
x
] for all r
∈
{
1,2
,
…
,
d
}, then the number of q-cycles(
N
) is equal to d.Proof.
We prove only part (i), for the other part is trivial from (38). If the number of q-cycles(
N
) is equal to d, the α-correspondence shows that the number of monic irreducible factors of x
N
-
1 is also d. The first assertion that each Q
N
r
(
x
)
∈
𝔽
q
[
x
] is irreducible follows at once from (38). This is also the case if q is a primitive root mod N
r for all r
∈
{
1,2
,
…
,
d
} which is a direct consequence of [3, Theorem 2.47(ii)].
From (38), we see that Q
N
r divides x
N
r
-
1. If ord(
Q
N
r
)
=
j
<
N
r, then Q
N
r divides x
j
-
1. Further, Lemma 3.6 of [3] shows that j
∣
N, and so x
j
-
1 divides x
N
-
1. The first assertion then implies that each cyclotomic factor of x
N
r
-
1 and of x
j
-
1 (as in (38)) is irreducible. Since gcd
(
N
r
,
q
)
=
1, the polynomial x
N
r
-
1 contains no multiple root and so all its irreducible factors are distinct. But the cyclotomic factorization of x
j
-
1 (as in (38)) does not contain the irreducible factor Q
N
r (because N
r
∤
j), which is a contradiction.Our next proposition, which shows how the number ofq-cycles can be used to generate irreducible polynomials, is based on the following known results.(i)
(Berlekamp's factorization theorem, [3, Theorem 4.1]). If f
∈
𝔽
q
[
x
] is monic and h
∈
𝔽
q
[
x
] is such that h
q
≡
h mod
⁡ f, then f
(
x
)
=
∏
c
∈
𝔽
q
‍
gcd
(
f
(
x
)
,
h
(
x
)
-
c
).
(ii)
(see [1, Theorem 9.13]) For each q-cycle(
N
)
(
a
0
,
a
1
,
…
,
a
ℓ
-
1
), if g
(
x
)
=
x
a
0
+
x
a
1
+
⋯
+
x
a
ℓ
-
1, then g
(
x
)
q
≡
g
(
x
) mod
⁡ (
x
N
-
1
). Combining these two results, we get the following.Proposition 14.
Let(
a
0
,
a
1
,
…
,
a
ℓ
-
1
) be a q-cycle(
N
), and g
(
x
)
=
x
a
0
+
x
a
1
+
⋯
+
x
a
ℓ
-
1. If the number of q-cycles(
N
) is equal to q, and if gcd
(
x
N
-
1
,
g
(
x
)
-
c
)
≠
1 for all c
∈
𝔽
q, then each polynomial gcd
(
x
N
-
1
,
g
(
x
)
-
c
) is irreducible over 𝔽
q.


## 3.1. Counting Formulae

Working withq-cycles, apart from the known result, [3, Theorem 3.5], that the number of monic irreducible f
∈
𝔽
q
[
x
], f
(
0
)
≠
0 for which ord(
f
)
=
N
r
(
r
∈
{
1
,
…
,
d
}
) and deg
⁡
(
f
)
=
o
N
r
(
q
) is φ
(
N
r
)
/
o
N
r
(
q
), some new information about the number of monic irreducible polynomials is now derived.Theorem 8.
(i) The polynomialf
∈
𝔽
q
[
x
] constructed via (2) from a q
(
a
)-cycle(
N
) with gcd
(
a
,
N
)
=
N
r
(
r
∈
{
1
,
…
,
d
}
) is a monic irreducible polynomial with f
(
0
)
≠
0,  ord
(
f
)
=
N
/
N
r and deg
⁡
(
f
)
=
o
N
/
N
r
(
q
). Conversely, each irreducible polynomial f
∈
𝔽
q
[
x
] with f
(
0
)
≠
0, ord
(
f
)
=
N
r and deg
⁡
(
f
)
=
o
N
r
(
q
) is an irreducible factor of x
N
-
1 arisen, through (2), from an q
(
a
)-cycle(
N
) with gcd
(
a
,
N
)
=
N
/
N
r.
(ii) The set of monic, irreduciblef
∈
𝔽
q
[
x
], f
(
0
)
≠
0 for which ord
(
f
)
∣
N is identical with the set of irreducible factors of x
N
-
1.
(iii) The number ofq-cycles(
N
), the number of monic irreducible factors of x
N
-
1, and the number of monic irreducible f
∈
𝔽
q
[
x
] with f
(
0
)
≠
0 and ord
(
f
)
∣
N are all equal to ∑
r
=
1
d
‍
φ
(
N
r
)
/
o
N
r
(
q
).Proof.
From Theorem1(v), each q
(
a
)-cycle(
N
) with gcd
(
a
,
N
)
=
N
r has length o
N
/
N
r
(
q
) and it thus gives rise, through the α-correspondence, to a monic irreducible f
∈
𝔽
q
[
x
], f
(
0
)
≠
0, of degree o
N
/
N
r
(
q
). Each root of f is of the form α
a
q
i
(
i
∈
{
0,1
,
…
,
o
N
/
N
r
(
q
)
-
1
}
) where α is a primitive Nth root of unity, and so its order is N
/
N
r. Part (i) is thus a consequence of [3, Theorem 3.3] and the α-correspondence.
To prove (ii), note that if the monic irreduciblef
∈
𝔽
q
[
x
] satisfies f
(
0
)
≠
0 and ord(
f
)
∣
N, then ord(
f
)
=
N
r for some r
∈
{
1
,
…
,
d
}. Thus, f
∣
(
x
N
r
-
1
), and so f
∣
(
x
N
-
1
). On the other hand, if f is an irreducible factor of x
N
-
1, the α-correspondence assures us that f is constructed from a q-cycle(
N
) and the desired conclusion follows from (i).
Part (iii) follows (ii), theα-correspondence, and Theorem 1(viii).There is another straightforward technique to derive a formula for the number of monic irreducible polynomials of fixed order usingq-cycles based on the inclusion-exclusion principle. Although the formula so obtained is not easy to use, we give a proof to illustrate this different approach. For r
∈
{
1,2
,
…
,
d
}, set (keeping the earlier notation in the first section)
(30)
ℐ
N
r
=
{
monic
irreducible
polynomials
arising
from
d
the
q
-cycles
(
N
r
)
as
constructed
in
(
2
)
}
,
𝒪
N
d
=
𝒪
1
=
|
𝒞
1
|
,
𝒪
N
r
=
|
𝒞
N
r
|
-
∑
M
∣
N
r
,
M
<
N
r
‍
𝒪
M
.
For a given s
∈
ℕ and distinct primes p
1
,
p
2
,
…
,
p
k, define
(31)
〈
s
〉
≔
{
p
1
n
1
p
2
n
2
⋯
p
k
n
k
;
n
1
,
n
2
,
…
,
n
k
∈
ℕ
,
d
n
1
+
n
2
+
⋯
+
n
k
=
s
}
.Proposition 9.
LetN
=
p
1
n
1
p
2
n
2
⋯
p
k
n
k, the unique prime factorization of N. The number of monic, irreducible polynomials f
∈
𝔽
q
[
x
]
∖
𝔽
q, f
(
0
)
≠
0 having order N is equal to
(32)
𝒪
N
=
|
ℐ
N
1
|
-
|
⋃
r
=
2
d
ℐ
N
r
|
(33)
=
|
𝒞
N
1
|
-
{
∑
r
=
2
d
‍
|
𝒞
N
r
|
ssssss
-
∑
x
1
,
x
2
∈
{
N
2
,
N
3
,
…
,
N
d
}
,
x
1
<
x
2
‍
|
𝒞
gcd
⁡
(
x
1
,
x
2
)
|
ssssss
+
⋯
+
(
-
1
)
d
ssssss
×
∑
x
1
,
x
2
,
…
,
x
d
-
1
∈
{
N
2
,
N
3
,
…
,
N
d
}
,
x
1
<
x
2
<
⋯
<
x
d
-
1
‍
|
𝒞
gcd
⁡
(
x
1
,
x
2
,
…
,
x
d
-
1
)
|
∑
r
=
2
d
‍
}
(34)
=
|
𝒞
N
1
|
-
∑
m
∈
〈
s
-
1
〉
‍
|
𝒞
m
|
+
∑
m
∈
〈
s
-
2
〉
‍
|
𝒞
m
|
+
⋯
+
(
-
1
)
k
∑
m
∈
〈
s
-
k
〉
‍
|
𝒞
m
|
.Proof.
Since the number of distinct irreducible factors ofx
N
-
1 in 𝔽
q
[
x
] is equal to the number of q-cycles(
N
) [1, Corollary 9.12], from its definition, the α-correspondence and [3, Lemma 3.6], 𝒪
N
r is simply the number irreducible factors (in 𝔽
q
[
x
] constructed through (2)) of x
N
r
-
1 which are not irreducible factors of x
M
-
1 for any M
∣
N
r, M
<
N
r, which is in turn equivalent to saying that 𝒪
N
r is the number of monic, irreducible polynomials f
∈
𝔽
q
[
x
], f
(
0
)
≠
0, having order N
r, and this proves (32).
Again using [1, Corollary 9.12] and [3, Lemma 3.6] to translate the number of q-cycles to those of corresponding irreducible polynomials, the inclusion-exclusion formulae on the right-hand sides of (33) and (34) clearly yield the number of irreducible factors of x
N
-
1 which are not irreducible factors of x
N
r
-
1 for all r
∈
{
2,3
,
…
,
d
}, and this verifies (33) and (34).Remark 10.
Let us remark that there are no irreducible polynomials in𝔽
q
[
x
] of order n with gcd
(
q
,
n
)
>
1. This is seen as follows: for f
(
x
)
∈
𝔽
q
[
x
] with f
(
0
)
≠
0, since ord(
f
) is the least positive integer for which f
(
x
) divides x
ord
(
f
)
-
1, monic irreducible polynomials of order n are contained in the set of irreducible factors of x
n
-
1 in 𝔽
q
[
x
]. Putting n
=
N
p
e
(
e
∈
ℕ
,
gcd
(
q
,
N
)
=
1
), since x
n
-
1
=
(
x
N
-
1
)
p
e, the set of all irreducible factors of x
n
-
1 is identical with the set of all irreducible factors of x
N
-
1, and so each irreducible factor of x
n
-
1 is of order ≤
N
<
n.In contrast to the preceding remark, there always exists a (reducible) polynomial in𝔽
q
[
x
] of order n with gcd
(
q
,
n
)
>
1. This is seen as follows: using the terminology of the last remark, since gcd
(
q
,
N
)
=
1, Theorem 8 assures us that there always exists a monic, irreducible polynomial g
(
x
)
∈
𝔽
q
[
x
], g
(
0
)
≠
0, having ord
(
g
)
=
N. Consequently, Theorem 3.8 in [3] tells us that ord(
g
(
x
)
p
e
)
=
N
p
e
=
n.Our next task is to compute the number of monic polynomials in𝔽
q
[
x
] (both reducible and irreducible) having order N. Let f
(
x
)
∈
𝔽
q
[
x
] be a factor of the polynomial x
N
-
1 with ord(
f
)
=
N. Since gcd
(
q
,
N
)
=
1, the polynomial x
N
-
1 has no multiple factors. Assume that f
(
x
) is decomposed into k distinct monic irreducible factors (in 𝔽
q
[
x
]), say, f
(
x
)
=
f
1
(
x
)
⋯
f
k
(
x
). Since ord
(
f
)
=
N
=
lcm
{
ord
(
f
1
)
,
…
,
ord
(
f
k
)
}, each ord(
f
i
)
∈
{
N
=
N
1
>
N
2
>
⋯
>
N
d
=
1
} (the set of all divisors of N). Thus, the number of all such f's is equal to ∑
e
1
+
e
2
+
⋯
+
e
d
=
k
,
e
r
≥
0
,
lcm
(
N
r
;
e
r
≠
0
)
=
N
(
𝒪
N
1
e
1
)
⋯
(
𝒪
N
d
e
d
). We have thus proved.Theorem 11.
The total number of monic polynomials (both reducible and irreducible)f
∈
𝔽
q
[
x
], f
(
0
)
≠
0, having order N is
(35)
∑
k
=
1
m
‍
∑
e
1
+
e
2
+
⋯
+
e
d
=
k
,
e
r
≥
0
lcm
(
N
r
;
e
r
≠
0
)
=
N
‍
(
𝒪
N
1
e
1
)
⋯
(
𝒪
N
d
e
d
)
,
m
:
=
∑
r
=
1
d
‍
𝒪
N
r
.Having determined the number of polynomials with fixed order, it is natural to find out how many of them have orders dividing a fixedn
∈
ℕ.Theorem 12.
Letn
=
p
e
N
∈
ℕ with e
∈
ℕ
0 and gcd
(
q
,
N
)
=
1. Then the product of all monic irreducible polynomials f
∈
𝔽
q
[
x
], f
(
0
)
≠
0 for which ord
(
f
)
∣
n is equal to x
N
-
1 and their number is equal to |
𝒞
N
|
=
∑
r
=
1
d
‍
φ
(
N
r
)
/
o
N
r
(
q
).Proof.
Sincex
n
-
1
=
(
x
N
-
1
)
p
e, the set of all monic irreducible factors of x
N
-
1 is identical with the set of all monic irreducible factors of x
n
-
1. From [3, Theorem 3.6], for f
∈
𝔽
q
[
x
], f
(
0
)
≠
0, we know that ord(
f
)
∣
n if and only if f
(
x
)
∣
(
x
n
-
1
). Thus, the set of all monic irreducible polynomials f
∈
𝔽
q
[
x
], f
(
0
)
≠
0 for which ord(
f
)
∣
n is identical with the set of all irreducible factors of x
n
-
1 which is also equal to the set of all irreducible factors of x
N
-
1. Since x
N
-
1 has no multiple root, the product of all monic irreducible polynomials f
∈
𝔽
q
[
x
], f
(
0
)
≠
0 for which ord(
f
)
∣
n is x
N
-
1 and the first assertion is established. The second assertion follows immediately from the first assertion and Theorem 8(iv).


## 3.2. Some Explicit Shapes

Having counted the number of monic irreducible polynomials of fixed order, we proceed to determine their explicit shapes. From [1, Corollary 9.12], we know that the number of irreducible factors of x
N
-
1 in 𝔽
q
[
x
] is equal to the number of q-cycles(
N
) formed by the N numbers 0,1
,
…
,
N
-
1. To determine explicit shapes of all monic, irreducible polynomials f
∈
𝔽
q
[
x
], f
(
0
)
≠
0, having order N, we consider the polynomial
(36)
f
(
x
)
=
(
x
-
α
a
0
)
(
x
-
α
a
1
)
⋯
(
x
-
α
a
ℓ
-
1
)
∈
𝔽
q
[
x
]
associated with the q-cycle(
N
)
(
a
0
,
a
1
,
…
,
a
ℓ
-
1
), where α is a primitive Nth root of unity. By definition, [3, Lemma 3.6] and [1, Theorem 9.11], among all such polynomials, those which do not divide x
N
r
-
1, r
∈
{
2,3
,
…
,
d
}, are all the sought after polynomials having order N.Although, the procedure just described is satisfactory in principle, in certain cases, more precise shapes can be given. For a positive integern not divisible by p, recall that the nth cyclotomic polynomial [3, page 64] is defined as
(37)
Q
n
(
x
)
=
∏
i
=
1
gcd
(
i
,
n
)
=
1
n
(
x
-
ζ
i
)
=
∏
i
∣
n
‍
(
x
i
-
1
)
μ
(
n
/
i
)
∈
𝔽
q
[
x
]
,
where ζ is a primitive nth root of unity and μ is the Möbius function. It is known that
(38)
x
N
-
1
=
∏
r
=
1
d
‍
Q
N
r
(
x
)
.Proposition 13.
Letd
=
d
(
N
) be the number of divisors of N. (i)
If the number ofq-cycles(
N
) is equal to d, then in (38) each Q
N
r
(
x
) is irreducible in 𝔽
q
[
x
] and ord
(
Q
N
r
)
=
N
r. In particular, Q
N
(
x
)
∈
𝔽
q
[
x
] is irreducible and of order N. The same conclusion holds if q is a primitive root mod N
r for all r
∈
{
1,2
,
…
,
d
}.
(ii)
IfQ
N
r
(
x
) is irreducible in 𝔽
q
[
x
] for all r
∈
{
1,2
,
…
,
d
}, then the number of q-cycles(
N
) is equal to d.Proof.
We prove only part (i), for the other part is trivial from (38). If the number of q-cycles(
N
) is equal to d, the α-correspondence shows that the number of monic irreducible factors of x
N
-
1 is also d. The first assertion that each Q
N
r
(
x
)
∈
𝔽
q
[
x
] is irreducible follows at once from (38). This is also the case if q is a primitive root mod N
r for all r
∈
{
1,2
,
…
,
d
} which is a direct consequence of [3, Theorem 2.47(ii)].
From (38), we see that Q
N
r divides x
N
r
-
1. If ord(
Q
N
r
)
=
j
<
N
r, then Q
N
r divides x
j
-
1. Further, Lemma 3.6 of [3] shows that j
∣
N, and so x
j
-
1 divides x
N
-
1. The first assertion then implies that each cyclotomic factor of x
N
r
-
1 and of x
j
-
1 (as in (38)) is irreducible. Since gcd
(
N
r
,
q
)
=
1, the polynomial x
N
r
-
1 contains no multiple root and so all its irreducible factors are distinct. But the cyclotomic factorization of x
j
-
1 (as in (38)) does not contain the irreducible factor Q
N
r (because N
r
∤
j), which is a contradiction.Our next proposition, which shows how the number ofq-cycles can be used to generate irreducible polynomials, is based on the following known results.(i)
(Berlekamp's factorization theorem, [3, Theorem 4.1]). If f
∈
𝔽
q
[
x
] is monic and h
∈
𝔽
q
[
x
] is such that h
q
≡
h mod
⁡ f, then f
(
x
)
=
∏
c
∈
𝔽
q
‍
gcd
(
f
(
x
)
,
h
(
x
)
-
c
).
(ii)
(see [1, Theorem 9.13]) For each q-cycle(
N
)
(
a
0
,
a
1
,
…
,
a
ℓ
-
1
), if g
(
x
)
=
x
a
0
+
x
a
1
+
⋯
+
x
a
ℓ
-
1, then g
(
x
)
q
≡
g
(
x
) mod
⁡ (
x
N
-
1
). Combining these two results, we get the following.Proposition 14.
Let(
a
0
,
a
1
,
…
,
a
ℓ
-
1
) be a q-cycle(
N
), and g
(
x
)
=
x
a
0
+
x
a
1
+
⋯
+
x
a
ℓ
-
1. If the number of q-cycles(
N
) is equal to q, and if gcd
(
x
N
-
1
,
g
(
x
)
-
c
)
≠
1 for all c
∈
𝔽
q, then each polynomial gcd
(
x
N
-
1
,
g
(
x
)
-
c
) is irreducible over 𝔽
q.


## 4. Degree of a Polynomial

We begin by listing (without proofs) known facts involving degrees of irreducible polynomials, which can be proved usingq-cycles.(i)
(see [3, Theorem 3.20]) The product of all monic irreducible f
∈
𝔽
q
[
x
], f
(
0
)
≠
0 for which deg
⁡
(
f
)
∣
n is equal to x
q
n
-
1
-
1.
(ii)
(see [3, Theorem 3.25]) The number of monic irreducible polynomials in 𝔽
q
[
x
] of degree ℓ is equal to (
1
/
ℓ
)
∑
k
∣
ℓ
‍
μ
(
k
)
q
ℓ
/
k.
(iii)
(see [3, Corollary 3.4]) The set of monic irreducible f
∈
𝔽
q
[
x
], f
(
0
)
≠
0 for which deg
⁡
(
f
)
∣
n is identical with the set of monic irreducible f
∈
𝔽
q
[
x
], f
(
0
)
≠
0 for which ord(
f
)
∣
(
q
n
-
1
). Moreover, for f
∈
𝔽
q
[
x
], f
(
0
)
≠
0, we have deg
⁡
(
f
)
∣
n if and only if ord(
f
)
∣
(
q
n
-
1
). Using q-cycles, that is, Theorem 1(viii) and the assertion [3, Theorem 3.20] the following new result is immediate.Theorem 15.
The number of monic irreducible polynomialsf
(
x
)
∈
𝔽
q
[
x
], f
(
0
)
≠
0 for which deg
⁡
(
f
)
∣
n is equal to |
𝒞
q
n
-
1
|
=
∑
M
∣
q
n
-
1
‍
φ
(
M
)
/
o
M
(
q
), where the definition of 𝒞
q
n
-
1 can be found in the heading “Notation and Terminology”.Combining Theorems15 and 2(iii), we obtain a nice arithmetical identity.Corollary 16.
One has∑
M
∣
(
q
n
-
1
)
‍
(
φ
(
M
)
/
o
M
(
q
)
)
=
∑
M
∣
n
‍
(
(
1
/
M
)
∑
k
∣
M
‍
μ
(
k
)
q
M
/
k
)
-
1.


## 5. Coefficients andq-Cycle

Since a givenq-cycle gives rise, through the α-correspondence, to a unique polynomial, we illustrate now how to uniquely determine all coefficients of its corresponding polynomial (2) and conversely.Theorem 17.
Letα be a primitive Nth root of unity, let m be the order of q
mod
⁡
N, and let ξ be a generator of  𝔽
q
m.(i)
If theq
(
a
0
)-cycle(
N
)
(
a
0
,
a
1
,
…
,
a
ℓ
-
1
) is given, then the coefficients of its corresponding polynomial in (2) h
(
x
)
=
(
x
-
α
a
0
)
(
x
-
α
a
1
)
⋯
(
x
-
α
a
ℓ
-
1
)
:
=
∑
k
=
0
ℓ
‍
(
-
1
)
k
c
k
x
ℓ
-
k
∈
𝔽
q
[
x
] are given by
(39)
c
0
=
1
,
c
k
=
∑
0
≤
i
0
<
i
1
<
⋯
<
i
k
-
1
≤
ℓ
-
1
‍
α
a
i
0
α
a
i
1
⋯
α
a
i
k
-
1
(
k
=
1
,
…
,
ℓ
)
.
(ii)
If the coefficients ofh
(
x
) are given, then the corresponding q-cycle is uniquely determined through its leading element which is found by solving for s, A, and a
0, respectively, from the system
(40)
ξ
s
=
(
-
1
)
ℓ
c
ℓ
,
(41)
(
q
m
-
1
N
)
A
≡
s
mod
⁡
q
m
-
1
,
(42)
a
0
(
1
+
q
+
⋯
+
q
ℓ
-
1
)
≡
A
mod
⁡
N
.Proof.
(i) The relations in (39) are simply the symmetric polynomial relations between the roots and coefficients of a polynomial.
(ii) It is trivial that eachq-cycle is uniquely determined from its leading element. Next, note that (40) is simply a representation of element in 𝔽
q
m. Through the α-correspondence, the q-cycle (
a
0
,
a
1
,
…
,
a
ℓ
-
1
) associated with h
(
x
) must satisfy
(43)
ξ
s
=
(
-
1
)
ℓ
c
ℓ
=
α
t
,
t
∶
=
a
0
+
a
1
+
⋯
+
a
ℓ
-
1
≡
a
0
(
1
+
q
+
⋯
+
q
ℓ
-
1
)
mod
⁡
N
.
The conclusion follows from the facts that α
=
ξ
(
q
m
-
1
)
/
N and that solving (41) and (42) yields a
0 uniquely mod N.


## 6. Primitive and Self-Reciprocal Polynomials

We now apply preceding results to two special cases, corresponding toN
=
q
n
-
1 and N
=
q
m
+
1, to deduce a number of results about primitive and self-reciprocal polynomials.


### 6.1. Primitive Polynomials

Recall from [3, Definition 3.15] that a primitive polynomial of degree n
∈
ℕ over 𝔽
q is the minimal polynomial over 𝔽
q of a primitive element of 𝔽
q
n. We mention, without proofs, some known results provable using q-cycles.(1)
(see [3, Theorem 3.16]) An irreducible polynomial f
(
x
)
∈
𝔽
q
[
x
] of degree n is primitive if and only if f is monic, f
(
0
)
≠
0 and ord(
f
)
=
q
n
-
1. In other words, each primitive polynomial in 𝔽
q
[
x
] of degree n can be constructed from a q
(
a
)-cycle(
q
n
-
1
) with gcd
(
a
,
q
n
-
1
)
=
1 through (2). Conversely, for each q
(
a
)-cycle(
q
n
-
1
) with gcd
(
a
,
q
n
-
1
)
=
1, the polynomial (2) is a primitive polynomial in 𝔽
q
[
x
] of degree n.
(2)
(see [1, Theorem 7.7]) The number of primitive polynomials in 𝔽
q
[
x
] of degree n is φ
(
q
n
-
1
)
/
n, which equals to the number of q
(
a
)-cycle(
q
n
-
1
) with gcd
(
a
,
q
n
-
1
)
=
1.


### 6.2.  Self-Reciprocal Polynomials

Letf
(
x
)
=
a
n
x
n
+
a
n
-
1
x
n
-
1
+
⋯
+
a
1
x
+
a
0
∈
𝔽
q
[
x
] with a
n
≠
0. The reciprocal polynomial f
* of f is defined by f
*
(
x
)
=
x
n
f
(
1
/
x
)
=
a
0
x
n
+
a
1
x
n
-
1
+
⋯
+
a
n
-
1
x
+
a
n. A nonzero polynomial f
∈
𝔽
q
[
x
] is called self-reciprocal if f
(
x
)
=
f
*
(
x
)
:
=
x
n
f
(
1
/
x
). We confine ourselves here to the study of self-reciprocal irreducible monic (srim) polynomials in 𝔽
q
[
x
]. Since there is only one first degree srim-polynomial, namely, x
+
1, throughout the rest of this section we treat only srim-polynomials of degree ≥2. We next mention a known characterization and results about srim-polynomials provable via q-cycles.(i)
(see [2, page 275]) Let f
∈
𝔽
q
[
x
] be irreducible and monic of degree ≥2. Then f is self-reciprocal if and only if its set of roots (each of which is evidently non-zero) is closed under inversion (and so its degree must be even).
(ii)
(see [2, Proposition 3]) If f
∈
𝔽
q
[
x
] is a srim-polynomial with deg
⁡
(
f
)
=
2
m, then ord(
f
)
∣
(
q
m
+
1
) but ord(
f
)
∤
(
q
k
+
1
) for all k
∈
{
0,1
,
…
,
m
-
1
}.
(iii)
(see [4, Lemma 2.3], [5, Theorem 1(i)], [2, Corollary 5]) For a
∈
ℤ
q
m
+
1 with gcd
(
a
,
q
m
+
1
)
=
N
r
(
r
∈
{
1
,
…
,
d
}
), each q
(
a
)-cycle(
q
m
+
1
), which is of length o
N
/
N
r
(
q
)
=
2
m, gives rise through (2) to a srim-polynomial in 𝔽
q
[
x
] of degree 2
m and order dividing q
m
+
1. Conversely, each srim-polynomial f
∈
𝔽
q
[
x
] of degree 2
m arises via (2) from a q
(
a
)-cycle(
q
m
+
1
) with length o
(
q
m
+
1
)
/
N
r
(
q
)
=
2
m and ord(
f
)
∣
(
q
m
+
1
), where N
r
=
gcd
(
a
,
q
m
+
1
).
(iv)
(see [5, Theorem 1(ii)]) Each irreducible factor f
(
x
) of x
q
m
+
1
-
1 with deg
⁡
(
f
)
≥
2 is a srim-polynomial with deg
⁡
(
f
)
=
2
k, where k
∣
m and m
/
k is odd. We next prove two new results using q-cycles.Theorem 18.
(i) For each divisorN
r of q
m
+
1, the number of all srim-polynomial's f
∈
𝔽
q
[
x
] for which ord
(
f
)
=
N
r and deg
⁡
(
f
)
=
o
N
r
(
q
) is φ
(
N
r
)
/
o
N
r
(
q
).
(ii) The number of srim-polynomials of degree2
m in 𝔽
q
[
x
] is equal to (
1
/
2
m
)
∑
1
≤
r
≤
d
,
o
N
r
(
q
)
=
2
m
‍
φ
(
N
r
).Proof.
(i) and (ii) follow from [4, Lemma 2.3], [5, Theorem 1(ii)], Theorem 4, [3, Theorem 3.5], and Theorem 8(ii).Combining [2, Proposition 3], [5, Theorem 1(i)-(ii)], and Theorem 18 with results in Section 2, we obtain the following known results about the set D
m as defined in (11).(i)
(see [2, Proposition 4]) Assume that f is a srim-polynomial over 𝔽
q of degree 2
m and let α
∈
𝔽
q
2
m be a root of f. Then α is a primitive Dth root of unity for some D
∈
D
m.
(ii)
(see [3, Exercise 3.15, page 141]) If f is a srim-polynomial in 𝔽
q
[
x
] of degree >1 and order e, then every monic irreducible polynomial in 𝔽
q
[
x
] of degree >1 whose order divides e is self-reciprocal.
(iii)
(see [2, Corollary 5], [6, Theorem 2]) If f is a srim-polynomial of degree 2
m over 𝔽
q, then ord(
f
)
∈
D
m.
(iv)
(see [2, Proposition 7]) Let D
∈
D
m and let β be a primitive Dth root of unity. If f
β
(
x
)
=
∏
i
=
0
2
m
-
1
‍
(
x
-
β
q
i
), then the polynomial f
β is an srim-polynomial of degree 2
m and order D.
(v)
(see [2, Theorem 8]) For a monic irreducible polynomial f of degree 2
m over 𝔽
q, the following statements are equivalent.
(1)
f is self-reciprocal.
(2)
ord(
f
)
∈
D
m.
(3)
f
=
f
β for some primitive Dth root of unity β, with D
∈
D
m.
(vi)
(see [2, Theorem 9])
(1)
There areφ
(
D
)
/
2
m srim-polynomials in 𝔽
q
[
x
] of degree 2
m and order D for each D
∈
D
m.
(2)
The number of srim-polynomials in𝔽
q
[
x
] of degree 2
m is (
1
/
2
m
)
∑
D
∈
D
m
‍
φ
(
D
).
(vii)
(see [2, Theorem 11]) For D
∈
D
m, the Dth cyclotomic polynomial Q
D factors into the product of all srim-polynomials over 𝔽
q of degree 2
m and order D.
(viii)
(see [5, Theorem 3]) Let S
q
(
m
) denote the number of srim-polynomials of degree 2
m over 𝔽
q. Then
(44)
S
q
(
m
)
=
{
q
m
-
1
2
m
,
if
q
is
odd
,
m
=
2
s
;
1
2
m
∑
d
∣
m
d
odd
μ
(
d
)
q
m
/
d
,
otherwise
.


## 6.1. Primitive Polynomials

Recall from [3, Definition 3.15] that a primitive polynomial of degree n
∈
ℕ over 𝔽
q is the minimal polynomial over 𝔽
q of a primitive element of 𝔽
q
n. We mention, without proofs, some known results provable using q-cycles.(1)
(see [3, Theorem 3.16]) An irreducible polynomial f
(
x
)
∈
𝔽
q
[
x
] of degree n is primitive if and only if f is monic, f
(
0
)
≠
0 and ord(
f
)
=
q
n
-
1. In other words, each primitive polynomial in 𝔽
q
[
x
] of degree n can be constructed from a q
(
a
)-cycle(
q
n
-
1
) with gcd
(
a
,
q
n
-
1
)
=
1 through (2). Conversely, for each q
(
a
)-cycle(
q
n
-
1
) with gcd
(
a
,
q
n
-
1
)
=
1, the polynomial (2) is a primitive polynomial in 𝔽
q
[
x
] of degree n.
(2)
(see [1, Theorem 7.7]) The number of primitive polynomials in 𝔽
q
[
x
] of degree n is φ
(
q
n
-
1
)
/
n, which equals to the number of q
(
a
)-cycle(
q
n
-
1
) with gcd
(
a
,
q
n
-
1
)
=
1.


## 6.2.  Self-Reciprocal Polynomials

Letf
(
x
)
=
a
n
x
n
+
a
n
-
1
x
n
-
1
+
⋯
+
a
1
x
+
a
0
∈
𝔽
q
[
x
] with a
n
≠
0. The reciprocal polynomial f
* of f is defined by f
*
(
x
)
=
x
n
f
(
1
/
x
)
=
a
0
x
n
+
a
1
x
n
-
1
+
⋯
+
a
n
-
1
x
+
a
n. A nonzero polynomial f
∈
𝔽
q
[
x
] is called self-reciprocal if f
(
x
)
=
f
*
(
x
)
:
=
x
n
f
(
1
/
x
). We confine ourselves here to the study of self-reciprocal irreducible monic (srim) polynomials in 𝔽
q
[
x
]. Since there is only one first degree srim-polynomial, namely, x
+
1, throughout the rest of this section we treat only srim-polynomials of degree ≥2. We next mention a known characterization and results about srim-polynomials provable via q-cycles.(i)
(see [2, page 275]) Let f
∈
𝔽
q
[
x
] be irreducible and monic of degree ≥2. Then f is self-reciprocal if and only if its set of roots (each of which is evidently non-zero) is closed under inversion (and so its degree must be even).
(ii)
(see [2, Proposition 3]) If f
∈
𝔽
q
[
x
] is a srim-polynomial with deg
⁡
(
f
)
=
2
m, then ord(
f
)
∣
(
q
m
+
1
) but ord(
f
)
∤
(
q
k
+
1
) for all k
∈
{
0,1
,
…
,
m
-
1
}.
(iii)
(see [4, Lemma 2.3], [5, Theorem 1(i)], [2, Corollary 5]) For a
∈
ℤ
q
m
+
1 with gcd
(
a
,
q
m
+
1
)
=
N
r
(
r
∈
{
1
,
…
,
d
}
), each q
(
a
)-cycle(
q
m
+
1
), which is of length o
N
/
N
r
(
q
)
=
2
m, gives rise through (2) to a srim-polynomial in 𝔽
q
[
x
] of degree 2
m and order dividing q
m
+
1. Conversely, each srim-polynomial f
∈
𝔽
q
[
x
] of degree 2
m arises via (2) from a q
(
a
)-cycle(
q
m
+
1
) with length o
(
q
m
+
1
)
/
N
r
(
q
)
=
2
m and ord(
f
)
∣
(
q
m
+
1
), where N
r
=
gcd
(
a
,
q
m
+
1
).
(iv)
(see [5, Theorem 1(ii)]) Each irreducible factor f
(
x
) of x
q
m
+
1
-
1 with deg
⁡
(
f
)
≥
2 is a srim-polynomial with deg
⁡
(
f
)
=
2
k, where k
∣
m and m
/
k is odd. We next prove two new results using q-cycles.Theorem 18.
(i) For each divisorN
r of q
m
+
1, the number of all srim-polynomial's f
∈
𝔽
q
[
x
] for which ord
(
f
)
=
N
r and deg
⁡
(
f
)
=
o
N
r
(
q
) is φ
(
N
r
)
/
o
N
r
(
q
).
(ii) The number of srim-polynomials of degree2
m in 𝔽
q
[
x
] is equal to (
1
/
2
m
)
∑
1
≤
r
≤
d
,
o
N
r
(
q
)
=
2
m
‍
φ
(
N
r
).Proof.
(i) and (ii) follow from [4, Lemma 2.3], [5, Theorem 1(ii)], Theorem 4, [3, Theorem 3.5], and Theorem 8(ii).Combining [2, Proposition 3], [5, Theorem 1(i)-(ii)], and Theorem 18 with results in Section 2, we obtain the following known results about the set D
m as defined in (11).(i)
(see [2, Proposition 4]) Assume that f is a srim-polynomial over 𝔽
q of degree 2
m and let α
∈
𝔽
q
2
m be a root of f. Then α is a primitive Dth root of unity for some D
∈
D
m.
(ii)
(see [3, Exercise 3.15, page 141]) If f is a srim-polynomial in 𝔽
q
[
x
] of degree >1 and order e, then every monic irreducible polynomial in 𝔽
q
[
x
] of degree >1 whose order divides e is self-reciprocal.
(iii)
(see [2, Corollary 5], [6, Theorem 2]) If f is a srim-polynomial of degree 2
m over 𝔽
q, then ord(
f
)
∈
D
m.
(iv)
(see [2, Proposition 7]) Let D
∈
D
m and let β be a primitive Dth root of unity. If f
β
(
x
)
=
∏
i
=
0
2
m
-
1
‍
(
x
-
β
q
i
), then the polynomial f
β is an srim-polynomial of degree 2
m and order D.
(v)
(see [2, Theorem 8]) For a monic irreducible polynomial f of degree 2
m over 𝔽
q, the following statements are equivalent.
(1)
f is self-reciprocal.
(2)
ord(
f
)
∈
D
m.
(3)
f
=
f
β for some primitive Dth root of unity β, with D
∈
D
m.
(vi)
(see [2, Theorem 9])
(1)
There areφ
(
D
)
/
2
m srim-polynomials in 𝔽
q
[
x
] of degree 2
m and order D for each D
∈
D
m.
(2)
The number of srim-polynomials in𝔽
q
[
x
] of degree 2
m is (
1
/
2
m
)
∑
D
∈
D
m
‍
φ
(
D
).
(vii)
(see [2, Theorem 11]) For D
∈
D
m, the Dth cyclotomic polynomial Q
D factors into the product of all srim-polynomials over 𝔽
q of degree 2
m and order D.
(viii)
(see [5, Theorem 3]) Let S
q
(
m
) denote the number of srim-polynomials of degree 2
m over 𝔽
q. Then
(44)
S
q
(
m
)
=
{
q
m
-
1
2
m
,
if
q
is
odd
,
m
=
2
s
;
1
2
m
∑
d
∣
m
d
odd
μ
(
d
)
q
m
/
d
,
otherwise
.



---

*Source: 823567-2014-02-26.xml*