Lattice Basis Reduction

266 Lattice Basis Reduction

Theorem 15. 9. Let q = p

n

as above, and let i ≥ 1. In F

q

[x] the polynomial

x

q

i

−x is the product of al l monic irreducibles whose degrees are divisors of i:

x

q

i

− x =

Y

d | i

Y

deg(f ) = d

f monic irreducible

f . (15.2)

Proof. We write g = x

q

i

−x for the left side of equation (15.2). We first observe

that g is squarefree by Lemma 15.6: clearly g

′

= −1 and so gcd(g, g

′

) = 1.

Suppose that f ∈ F

q

[x] is a monic irre ducible with deg (f ) = d. We will

show that if f is a divisor of g then d is a divisor of i. Since g is squarefree,

this will imply that g is a divisor of the right side of equation (15.2). If f is a

divisor of g then Lemma