# Polynomials in $\mathbb Z_2[x]$

Determine which polynomials in $\mathbb Z_2[x]$ have roots in $\mathbb Z_2$. I don't know how to solve this, but found that that it may be helpful to use the factor theorem, but since I haven't studied that theorem, I can't use it. Is there another way to prove this?

-

Let $f\in \mathbb Z_2[x]$. Clearly if the constant term of $f$ is $0$, then $0$ is a root of $f$. Otherwise $f(0)=1$. If $f$ has an even number of non-zero terms then $f(1)=0$, and otherwise $f(1)=1$. Thus $f$ has a root in $\mathbb Z_2$ if and only if $f$ has a constant term of $0$ or an even number of non-zero terms.

-

Hint $\$ See the discussion below, excerpted from one of my old sci.math posts.

If an integer coefficient polynomial has an integer root $\rm\,n,\,$ i.e.$\rm\ p(n) = 0,\$ then $\rm\,n\,$ remains a root modulo $2$, i.e. $\rm\ p(n)\equiv 0\,\ (mod\ 2).\:$ So, contrapositively, if a polynomial has no roots modulo $2$ then it has no integer roots. This leads to the following simple

Parity Root Test $\$ A polynomial $\rm\:P(x)\:$ with integer coefficients has no integer roots if its constant coefficient and coefficient sum are both odd.

Proof $\$ The test verifies that $\rm\ P(0) \equiv 1\equiv P(1)\ \ (mod\ 2)\:,\$ i.e. that $\rm\:P(x)\:$ has no roots modulo $2$, hence no integer roots. $\$ QED

E.g. $\rm\:\ a\ X^2 + b\ X + c\$ has no integer roots if $\rm\:c\:$ is odd and $\rm\:a,\:b\:$ have equal parity $\rm\:a\equiv b\ (mod\ 2)$

The Parity Root Test generalizes to any ring with a sense of parity, e.g. the Gaussian integers $\rm\: a + b\,{\it i}\$ for integers $\rm\:a,b.\:$ For much further discussion see this post and also these related posts.

-