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 = pn, and let k = qm. The irreducible factors of xk - 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 then
f(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, then
g(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 Iq(m).
The following formula for Iq(m) is due to Gauss.
Theorem 6.6.9. For any prime power q and any positive integer m,
Iq(m) = 1/m d | m ( m / d ) qd.
Corollary 6.6.10. For all positive integers m and all prime powers q we have Iq(m)1.
Forward to §6.7 | Back to §6.5 | Up | Table of Contents