Excerpted from Beachy/Blair, Abstract Algebra, 2nd Ed. © 1996

## § 6.6 Irreducible polynomials over finite fields

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:

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

```

```