# Number of irreducible quadratic polynomials over a finite field [duplicate]

This question already has an answer here:

To find the number of irreducible polynomials of the form $x^{2} + ax+b$ over the field $F_{7}$ I manually checked all the possibilities and thus found the answer to be $21.$ Like $b=0$ is not possible or taking $b=1$ and checking what values of $a$ works here etc. Surely it was tedious and time-consuming process and I don't think it was appropriate either. For what should be done for a much larger field$?$ Are there some basic theories that I should use. Hints please.

## marked as duplicate by Jyrki Lahtonen abstract-algebra StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Dec 12 '15 at 8:41

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

• You may want to check out mathoverflow.net/questions/101464/… – Anurag A Aug 11 '15 at 16:09
• To count, find the number of monic reducibles. That's easy, they are $(x-a)(x-b)$ where $a,b$ are distinct or equal. – André Nicolas Aug 11 '15 at 16:12
• Let the field have $N$ elements. There are $N^2$ monic quadratics, and $\binom{N}{2}+N$ reducibles among them, so $N(N-1)/2$ irreducibles. – André Nicolas Aug 11 '15 at 16:23
• The formula for the number of irreducible polynomials over a finite field and of a given degree has appeared on our site many times. Go ahead and search! – Jyrki Lahtonen Dec 12 '15 at 8:40

## 3 Answers

Regardless of the field, if a monic polynomial $$x^2+ax+b$$ is given then it can be reducible in two different ways:

$$(x-p)(x-q);p\neq q\\\text{or}\\(x-p)(x-q)={(x-p)}^2;p=q$$

If the field has cardinality $$N$$, then the total number of quadratic monic polynomials is $$N^2$$. There are $$\binom{N}{2}$$ (Combination without repetition) ways of choosing $$\{p,q\}$$ in the first case and $$N$$ ways in the second. We can conclude that the number of reducible polynomials is $${\binom{N}{2}}+N\\={{{N(N+1)}}\over 2}$$ So the number of irreducible polynomials is $$N^2-{{{N(N+1)}}\over 2}\\=N\cdot{{N-1}\over 2}$$

Since $$N$$ was arbitrary the claim follows.

The number of monic quadratic polynomials over $\Bbb{F}_q$ is $q^2$; they are the polynomials $$X^2+aX+b,$$ with $a,b\in\Bbb{F}_q$. If a monic quadratic polynomial $P\in\Bbb{F}_q[X]$ is reducible then $$P(X)=(X-a)(X-b),$$ for some $a,b\in\Bbb{F}_q$. So how many reducible monic quadratic polynomials are there?

There are $\tfrac{1}{2}q(q+1)$ reducible monic quadratic polynomials in $\Bbb{F}_q$. This yields a total of $\tfrac{1}{2}q(q-1)$ irreducible monic quadratic polynomials in $\Bbb{F}_q[X]$. For $q=7$ we indeed get $21$ such polynomials.

• I like your use of "invisible ink" - it's great pedagogical tool. – cactus314 Aug 11 '15 at 16:21

In any field (characteristic $\neq 2$) the quadratic formula still holds. The equation: $x^2 + ax + b = 0$ has two solutions:

$$x = \frac{-a \pm \sqrt{a^2 - 4b}}{2}$$

Then as $(a,b) \in \mathbb{F}_7^2$ how many of these have $a^2 - 4b$ a quadratic residue? Since $4$ is invertible mod $7$

$$a^2 - 4 \,\mathbb{F}_7 = \mathbb{F}_7$$

If we replace $7$ with a large prime $p \gg 1$ the odds of being a quadratic residue approach $\frac{1}{2}$.

What does the quadratic formula look like in characteristic 2? In $\mathbb{F}_2$ it is easy enough to check by hand. There are also finite fields with $2^n$ elements such as $\mathbb{F}_8$ which are also characteristic 2.

• What about fields of characteristic $2$? And I don't see how this answers the question exactly... – Servaes Aug 11 '15 at 16:18
• In $\mathbb{F}_2$, there are only 4 possibilities $x^2 , x^2 + 1=(x+1)^2, \color{blue}{x^2 + x + 1}, x^2 + x = x(x+1)$ – cactus314 Aug 11 '15 at 16:20
• I was referring to your opening remark; I meant that the quadratic formula does not hold in fields of characteristic $2$. – Servaes Aug 11 '15 at 16:21