Number of roots for a univariate polynomial in a finite field

abstract-algebrafinite-fields

I'm trying to prove a statement which seems obvious, but does not seem to be explicitly attested to anywhere:

Given a polynomial $f(x) = \sum_{i=0}^d a_i x^i$, where $a_i, x \in GF(q)$, with $q$ not necessarily prime, the equation $f(x) = 0$ has at most $d$ solutions $x \in GF(q)$.

My first thought is to use the Fundamental Theorem of Algebra: since $f(x)$ can have at most $d$ solutions over $\mathbb{C}$, a fortiori it can have at most $d$ solutions over $GF(q)$. However, this argument fails because solutions there are up to $d$ solutions to $f(x) = n2^q$ for $x \in \mathbb{C}, n \in \mathbb{Z}$, and those solutions would solve $f(x)$ in $GF(q)$ too. Also, after writing it out, I'm not sure if $GF(q)$ can be embedded in $\mathbb{C}$ so easily for a prime-power $q$ after all.

I've never taken a proper algebra course before (just a bit of discrete maths and a smattering of group/representation theory), so perhaps I may be missing something obvious, but a fairly extensive search has not turned up any leads on how to prove this. I've seen discussions on the roots for systems of equations, or equations in multiple variables, but no proof for this simple statement on a univariate polynomial. Factorising the polynomial doesn't really help either, because the polynomial might be irreducible. Any help would be appreciated!

Best Answer

The statement that a polynomial of degree $d$ has at most $d$ distinct roots is very general and easier to prove than e.g. the fundamental theorem of algebra (which says that a polynomial has exactly $d$ roots counted with multiplicity over $\mathbb{C}$). For example, it remains true when you replace $GF(q)$ by any integral domain.

Since $GF(q)$ is a field, there is a proof by induction that only uses the Euclidean division of polynomials with coefficients in $GF(q)$.

  • If $P$ is a (nonzero) polynomial of degree $0$, $P$ does not have any root.
  • Let $P$ be a polynomial of degree $d$. If $P$ has some root $a$, there exist two polynomials $Q$ and $R$ such that $R$ is of degree 0 and

$$P=(X-a)Q+R$$

Since $R(a)=0$, we have $R=0$. Let $b\neq a$ be another root of $P$. Then $(b-a)Q(b)=0$, and since $GF(q)$ is a field, $Q(b)=0$. So all roots of $P$ different from $a$ are also roots of $Q$. As $Q$ is of degree $d-1$, by induction it has at most $d-1$ roots. It follows that $P$ has at most $d$ roots.

Related Question