Knowing is a polynomial has a root in a finite field of $125$ elements

Question

I was looking at this post and saw a comment left without an answer that intrigued me. The question posed was about a field being isomorphic to a quotient ring and an answer showed that: $$\frac {\mathbb Z[x,y]}{(5,x^2-y,xy+x+1)}\cong \frac {\mathbb Z_5[x,y]}{(x^2-y,xy+x+1)}\cong\frac {\mathbb Z_5[x]}{(x^3+x+1)} $$ The comment left asked if there was an easy way to see if the polynomial $x^3+3x+2$ has a root in a finite field of $125$ elements. Is there a general way to show this for any function and any finite field?

Answer 1

$x^3+3x+2$ has no root mod $5$ and so is irreducible. Therefore, $\frac {\mathbb Z_5[x]}{(x^3+x+1)}$ is a field with $5^3=125$ elements which contains a root of $x^3+3x+2$.

Things are not always so easy. In general, a polynomial $f$ has a root in a finite field of order $q=p^n$ iff $\gcd(f,x^q-x)\ne1$ mod $p$. This can be settled with Euclid's algorithm, but is not suitable for hand computation for large $q$ and $f$.

Answer 2

The general question of whether a polynomial $\ p(x)\in\mathbb{F}_q[x]\ $ over a finite field $\ \mathbb{F}_q $ of order $\ q\ $ has any roots in $\ \mathbb{F}_q\ $ can be decided by computing the greatest common divisor of $\ p(x)\ $ and $\ x^q-x\ $.

If $\ g(x)=$$\,\gcd(\,p(x),$$\,x^q-x\,)\ $, then $\ p(x)\ $ has a root in $\ \mathbb{F}_q\ $ if and only if $\ \deg(g(x))>0\ $. When this is the case, $\ g(x)\ $ splits into linear factors over $\ \mathbb{F}_q\ $ whose roots comprise all those of $\ p(x)\ $ that lie in $\ \mathbb{F}_q\ $. The remaining roots of $\ p(x)\ $—namely those of $\ \frac{p(x)}{g(x)}\ $—will belong to some extension field $\ \mathbb{F}_{q^r}\ $ of $\ \mathbb{F}_q\ $ of degree $\ r>1\ $.

The roots of any irreducible factor of $\ p(x)\ $ of degree $\ d\ $ will belong to $\ \mathbb{F}_{q^d}\ $. Those roots which are primitive will not belong to any proper subfield of $\ \mathbb{F}_{q^d}\ $, but if $\ \alpha $ is a primitive root and $\ e\ $ a proper divisor of $\ d\ $ then $\ \alpha^e \ $ will be a root belonging to the proper subfield $\ \mathbb{F}_{q^\frac{d}{e}}\ $.

If $\ d_1, d_2,\dots,d_t\ $ are the degrees of the irreducible factors of $\ p(x)\ $, and $\ \ell=\text{lcm}(d_1, d_2,\dots,d_t)\ $, then $\ \mathbb{F}_{q^\ell}\ $ is the smallest field that contains all the roots of $\ p(x)\ $.