Find the number of elements for which polynomial is irreducible

Question

I have the following problem:

Find the number of elements $\alpha \in F_{83}$ in the field of 83 elements for which the polynomial $t^2+5t+\alpha$ is irreducible.

I tried finding the discriminant $25-4\alpha$ and setting $25-4\alpha<0$, but I couldn't get anything further out of the condition.

Can you please tell me which direction to go in?

Answer 1

The quadratic formula in this case tells us $t^2+5t+\alpha$ is irreducible iff the discriminant $\Delta=25-4\alpha$ is not a square in $\mathbb F_{83}$. The map $\mathbb F_{83}\to \mathbb F_{83}:\alpha\mapsto 25-4\alpha$ is a bijection and there are exactly $(83-1)/2=41$ elements not a square in $\mathbb F_{83}$. Thus, there are $41$ choices for $\alpha$ making $t^2+5t+\alpha$ irreducible.

---

P.S. In the real case, the condition $\Delta<0$ is equivalent to $\Delta$ not being a square, which might be the cause of your confusion.

Answer 2

You are heading on a good direction, the discriminant is a square iff the equation has a solution and thus being reducible in $F_{p}$, $p=83$. So the right thing to do is to look at for how many $\alpha$, $25-4\alpha$ is a non-square.

One way to do it is to use quadratic residue symbol, but if you know the arithmetic of the finite field, we know that the multiplicative group $F_p^\times=F_p-\{0\}$ is a cyclic group from a group theory exercise (a finite group $G$ is cyclic iff for every divisor $d||G|$, there is at most one subgroup of order $d$, and for fields, all finite multiplicative subgroups of order $d$ are solutions to the equation $x^d=1$ which has at most $d$ solutions, so there is at most one such subgroup.)

So since $F_p^\times$ is cyclic of order $p-1$, the elements in $F_p^\times$ divisible by $2$ is the subgroup of index $2$, i.e. $(F_p^\times)^2$, which contains $\frac{p-1}{2}$ square elements, so there are also $\frac{p-1}{2}$ non-squares in $F_p^\times$, these are all non-squares in $F_p$ since $0$ is a square. Now $\alpha\mapsto 25-4\alpha$ is bijective since $4$ is prime to $83$, so it gives $41$ $\alpha$ values that makes $25-4\alpha$ non-square.