# Show COMBINATORIALLY the number of irreducible monic polynomials is the number of primitive necklaces

Show that the number of monic irreducible polynomials of degree $$n$$ over a finite field of size $$q$$ is the same as the number of primitive necklaces of size $$n$$ with $$q$$ colors. I have the formula

$$M(q,n) = \sum\limits_{d|n} q^d \mu\Big(\frac{n}{d}\Big)$$

which counts primitive necklaces. The goal is to show this counts monic irreducibles over a finite field combinatorially. I can use Mobius inversion. I know this question has been asked before, but the previous answers require a lot of algebra.

I tried a special case when $$q = 3$$ and $$n = 2$$. Let the colors of the beads of a necklace be red (R), yellow (Y) and blue (B). Then the primitive necklaces are $$RY$$, $$RB$$ and $$YB$$. I computed the irreducible polynomials of degree $$2$$ as well, they are: $$x^2 + 1, x^2 + x + 2$$ and $$x^2 + 2x + 2$$. It is really unclear how I could map necklaces to these polynomials. If I just consider these as $$3$$-tuples then we have $$(1, 0, 1), (1, 1, 2)$$ and $$(1, 2, 2)$$ so it isn't even clear how to map the colors.

• What is a primitive necklace? – KReiser Nov 27 '18 at 1:01
• @KReiser A necklace is primitive if it cannot be obtained by repeating a smaller necklace. (So $RRRY$ is primitive, but $RRRR$ and $RYRY$ are not, for example.) – Théophile Nov 27 '18 at 1:15
• A necklace is a cyclic sequence of colored beads. A necklace is called primitive if it is aperiodic, i.e. no non-trivial cyclic permutation yields the same necklace. – RickyLiuWho Nov 27 '18 at 1:16
• mathoverflow.net/questions/769/… – Mike Earnest Feb 11 at 21:19