Say I want to find the number of monic irreducible polynomials in $\mathbb{F}_{3}[X]$ of degree 2, by using the following formula (Gauss formula?). How does the formula work?
There is no explanation of it in my book or examples with it, and I honestly doesn't understand how the sum works.
What are we summing over? Like what index are we summing over, where does the sum start and end? What do they mean by d divides n written in the lower index?
Best Answer
In your case, $n = 2$, $p = 3$. The expression $$ \sum_{d|n} $$ means that your index set consists precisely of the divisors of $n$. In this case, the index set corresponds to $d = 1$ and $d = 2$. So the formula in your case is just $$ N_2 = \frac{1}{2}\left(\mu(2) 3^1 + \mu(1) 3^2\right) = \frac{1}{2}\left(-3 + 9\right) = 3. $$
If instead $n = 4$, then the terms of your sum would be over $d = 1$, $d = 2$, and $d =4$. So the summation has three terms. If $n = 10$, the terms of the sum would be $d = 1$, $d = 2$, $d = 5$, and $d = 10$.
As for why the formula works, this link may be useful.