Let $g$ be an irreducible polynomial of degree $n$ over $\mathbb{Z}/p\mathbb{Z}$. $a$ is a generator of the group $(\mathbb{Z}/p\mathbb{Z}[x]/\langle g \rangle)^*$ if $(\mathbb{Z}/p\mathbb{Z}[x]/\langle g \rangle)^* = \{1, a, \ldots, a^{p^{\deg(g)} - 2}\}$. How many monic irreducible polynomials $h$ over $\mathbb{Z}/p\mathbb{Z}$ such that $h(a) = 0$ for some generator $a$ does exist?

My first observation is that all such polynomials must have degree $n$ since if there is an irreducible polynomial $h_0$ such that $\deg h_0 \neq \deg g$ and $h_0(a) = 0$ for a generator $a$ then $(\mathbb{Z}/p\mathbb{Z}[x]/\langle h_0 \rangle) \simeq \mathbb{Z}/p\mathbb{Z}(a) \simeq (\mathbb{Z}/p\mathbb{Z}[x]/\langle g \rangle)$. That's a contradiction since these two fields have different size. On the other hand, $x^{p^n}-x$ is the product of all monic irreducible polynomials with degree $d | n$. Thus it should contain all the polynomials we need as divisors. That's the point where I'm out of ideas.


These are called primitive polynomials. The multiplicative group of the finite field $\mathbb{F}_{p^n}$ is cyclic of order $p^n - 1$, and so it has $\varphi(p^n - 1)$ generators where $\varphi(-)$ is the Euler totient function (exercise). A primitive polynomial has $n$ roots, each of which is a generator (exercise), and distinct primitive polynomials share no roots because they're irreducible, so there are

$$\frac{\varphi(p^n - 1)}{n}$$

primitive polynomials for $\mathbb{F}_{p^n}$. (Exercise: without knowing that this counts primitive polynomials, why is this expression an integer?)

(Final exercise: show that the product of all of the primitive polynomials for $\mathbb{F}_{p^n}$ is congruent to $\Phi_{p^n - 1}(x) \bmod p$ where $\Phi_n(-)$ denotes a cyclotomic polynomial. Note that $\Phi_n(x)$ always has degree $\varphi(n)$.)

  • $\begingroup$ By the definition of the cyclotomic polynomial, each of the generators is a root of $\Phi_{p^n-1}$ and they're the only roots it has. Thus each of its irreducible divisors has only generator roots. On the other hand, as we know, each of these divisors is a primitive polynomial and no other primitive polynomials exist. Since each of these polynomials has degree $n$ there are $\phi(p^n-1)/n$ of them. Am I right that it proves that all roots of a primitive polynomial are generators? $\endgroup$ – Artur Riazanov Jan 9 '18 at 3:26
  • 1
    $\begingroup$ Proving that all of the roots of a primitive polynomial are generators is easier than that: they are all Galois conjugates of a generator (more specifically, they are all obtained by acting via the Frobenius automorphisms), and automorphisms preserve the property of being a generator. $\endgroup$ – Qiaochu Yuan Jan 9 '18 at 3:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.