3
$\begingroup$

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.

$\endgroup$

marked as duplicate by Jyrki Lahtonen abstract-algebra 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.

  • 2
    $\begingroup$ You may want to check out mathoverflow.net/questions/101464/… $\endgroup$ – Anurag A Aug 11 '15 at 16:09
  • 1
    $\begingroup$ To count, find the number of monic reducibles. That's easy, they are $(x-a)(x-b)$ where $a,b$ are distinct or equal. $\endgroup$ – André Nicolas Aug 11 '15 at 16:12
  • 1
    $\begingroup$ 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. $\endgroup$ – André Nicolas Aug 11 '15 at 16:23
  • $\begingroup$ 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! $\endgroup$ – Jyrki Lahtonen Dec 12 '15 at 8:40
8
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

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

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.

See also: Number of monic irreducible polynomials of prime degree $p$ over finite fields

$\endgroup$
  • $\begingroup$ What about fields of characteristic $2$? And I don't see how this answers the question exactly... $\endgroup$ – Servaes Aug 11 '15 at 16:18
  • $\begingroup$ 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)$ $\endgroup$ – cactus314 Aug 11 '15 at 16:20
  • $\begingroup$ I was referring to your opening remark; I meant that the quadratic formula does not hold in fields of characteristic $2$. $\endgroup$ – Servaes Aug 11 '15 at 16:21

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