Forward to §6.7 | Back to §6.5 | Up | Table of Contents | About this document
Theorem 6.6.1.
Let F = GF(q), where q = p^{n}, and let k = q^{m}.
The irreducible factors of x^{k} - x
in F[x] are precisely the monic irreducible polynomials in F[x]
whose degree is a divisor of m.
Convention:
In the notation
_{d | n}
and
_{d | n}
we will assume that d | n refers to the positive divisors of n.
Definition 6.6.2.
If d is a positive integer, we define the
Moebius
function
(d) as follows:
Proposition 6.6.3.
If m, n are positive integers with gcd(m,n)=1, then
(mn) = (m) (n).
If R is a commutative ring, then a function
f : Z^{+} -> R
is said to be a
multiplicative
function if
f(mn) = f(m)f(n),
whenever gcd(m,n)=1.
Proposition 6.6.4.
Let R be a commutative ring, and let
f : Z^{+} -> R
be a multiplicative function. If
F : Z^{+} -> R
is defined by
F(n) = _{d | n} f(d),
for all n in Z^{+}, then F is a multiplicative function.
Proposition 6.6.5.
For any positive integer n,
_{d | n} (d) = 1 if n = 1, and
_{d | n} (d) = 0 if n > 1.
Theorem 6.6.6. [Moebius Inversion Formula]
Let R be a commutative ring, and let
f : Z^{+} -> R
be any function. If the function
F : Z^{+} -> R
is defined by
F(n) = _{d | n} f(d),
for all positive integers n thenf(m) = _{n | m} ( m/n ) F(n),
for all positive integers m.
Theorem 6.6.7. [Moebius Inversion Formula (2)]
Let R be a commutative ring, and let
g : Z^{+} -> R
be any function. If the function
G : Z^{+} -> R
is defined by
G(n) = _{d | n} g(d),
positive integers n, theng(m) = _{n | m} G(n)^{k},
for all positive integers m, where k = ( m/n ).
Definition 6.6.8.
The number of irreducible polynomials of degree m
over the finite field GF(q), where q is a prime power,
will be denoted by I_{q}(m).
The following formula for I_{q}(m) is due to Gauss.
Theorem 6.6.9.
For any prime power q and any positive integer m,
I_{q}(m) = 1/m _{d | m} ( m / d ) q^{d}.
Corollary 6.6.10.
For all positive integers m and all prime powers q we have
I_{q}(m)1.
Forward to §6.7 | Back to §6.5 | Up | Table of Contents