By consider the nonquadratic residues, one has an irreducible polynomial of degree $2$ over ${\Bbb F}_p$ for $p$ being odd: $x^2+r$. Also we know that $x^2+x+1$ is irreducible over ${\Bbb{F}_2}$. How can irreducible polynomials of degree $2$ over ${\Bbb F}_{p^n}$ in general look like?
For case when $p$ is odd, I'm wondering if we still have $x^2+r$ irreducible over $K:={\Bbb F}_{p^n}$ for some $r\in K$. But I don't see how to go on with this idea.
Best Answer
Let $p$ be odd. Then any element $a$ of a finite field $\mathbb{F}_{p^n}$ is a zero of a unique quadratic polynomial $X^2 - b$ with $b \in \mathbb{F}_{p^n}$. Since any such polynomial (except the one for $b=0$) has two zeroes that are distinct (the two zeroes are negatives of eachother and therefore distinct because $p$ is odd), there will be polynomials left that do not have any zeroes. Any such polynomial is irreducible.
A similar argument can be given for $p=2$, considering polynomials of the form $X^2 - X - b$, $b \in \mathbb{F}_{2^n}$. Such a polynomial has two distinct zeroes (its zeroes have sum $1$), and since an element of $\mathbb{F}_{2^n}$ is a root of at most one such a polynomial, there are irreducible polynomials of this form.