Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 4 down vote accepted

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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.