Exercise 1, § 12

a) Let $q$ be a power of a prime number. Show that for every integer $n > 1$, if $h_i$ ($1 \leq i \leq r$) are the distinct prime divisors of the integer $n$, then the number of elements $\zeta \in \mathbf{F}_{q^n}$ such that $\mathbf{F}_{q^n} = \mathbf{F}_q(\zeta)$ is equal to

(observe that such an element is characterized by the property of not belonging to any of the fields $\mathbf{F}_{q^{n/h_i}}$). If $h_1 \leq \ldots \leq h_r$, we have Examine the case where $n$ is a prime power. b) Let $b_n(q)$ be the number of monic irreducible polynomials of degree $n$ over $\mathbf{F}_q$. Deduce from a) an expression for $b_n(q)$. In particular, if $q \geq 3$, show that the number of polynomials (not necessarily monic) of degree $n$ in $\mathbf{F}_q[X]$ which are irreducible is at least equal to $q^n(q-2)/n \geq q^{n+1}/3n$. c) Prove that $\sum_{d|n} d b_d(q) = q^n$ (establish the identity $1/(1-qT) = \prod (1-T^n)^{-b_n(q)}$). \* Using the Mobius inversion formula (Lie, II, p. 176, Appendix), show that Compare this result with that obtained in b). d) Let $a_n(q)$ be the number of monic polynomials without multiple factors in $\mathbf{F}_q[X]$. Show that $a_0(q) = 1,\ a_1(q) = q,\ a_n(q) = q^n - q^{n-1}$ for $n > 1$ (establish the identity $q^n = \sum a_{n-2i}(q)\ q^i$).