Question about polynomials in finite fields

Question

No doubt I'm missing something obvious here (my finite field theory is quite rusty) but I'm reading a book that claims that

1) $f(x) = x^2 - x - 1$ is irreducible over $F_q$ where $q = p^e$ for an arbitrary prime $p$

2) If $\alpha$ is a root of $f$, then $\alpha^{q + 1} + 1 = 0$ and $\alpha^q + \alpha - 1 = 0$

and I'm having trouble seeing why this is true.

What am I missing here? Thanks!

Edit: As quid pointed out, $f$ is not always irreducible, so I guess that the proof this is contained in is not quite right.

Answer 1

I agree with Quid and professor Lubin in that in general $f(x)=x^2-x-1$ is NOT irreducible over $\Bbb{F}_q$. For example, if $q=5$, then $x=3$ is a double root, and $f(x)=(x-3)^2$.

OTOH, if it happens that $f(x)$ IS irreducible over $\Bbb{F}_q$, then, as $f$ is quadratic, its roots belong to $\Bbb{F}_{q^2}$. Furthermore, those roots are Galois conjugate of each other, so if $\alpha$ is one of them, then $\alpha^q$ is the other. In that case we have $$ x^2-x-1=f(x)=(x-\alpha)(x-\alpha^q)=x^2-(\alpha+\alpha^2)x+\alpha^{q+1}, $$ (just the good old Vieta relations) so the equations (2) do hold in that case.

Which case is it? Assume first $p>2$. The factorization of a quadratic depends on its discriminant. Here $$ D=b^2-4ac=(-1)^2-4\cdot1\cdot(-1)=5. $$ So $f$ is reducible if and only if $5$ has a square root in $\Bbb{F}_q$. This is the case if and only if one of the following (or both) holds:

• A) $5$ is a quadratic residue modulo $p$. By the law of quadratic reciprocity this happens iff $p$ is a quadratic residue modulo $5$, IOW $p=5$ or $p\equiv\pm1\pmod5$. Or,
• B) If $e$ is an even number. We always have $\sqrt5\in\Bbb{F}_{p^2}$, so when $2\mid e$ we automatically get $\sqrt5\in\Bbb{F}_q$.

If $p=2$, then $f(x)=x^2+x+1$ and its roots are known to be the primitive cubic roots of unity. Here case B is all we need, and $f$ is irreducible iff $2\nmid e$.