ABSTRACT ALGEBRA: OnLine Study Guide, Section 6.6

Forward to §6.7 | Back to §6.5 | Up | Table of Contents | About this document

§ 6.6 Irreducible polynomials over finite fields

Theorem 6.6.1. Let F = GF(q), where q = pⁿ, 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:

(1) = 1;

(d) = 1 if d has an even number of prime factors (each occurring only once);

(d) = -1 if d has an odd number of prime factors (each occurring only once);

(d) = 0 if d is divisible by the square of a prime.

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 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