Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

polynomial $X^n+a_1X^{n-1}+...+a_n \in \Bbb Z_2[X]$ doesn't have linear factors

$\iff a_n(1+\sum a_i) \neq 0$.

How then $f(X)=X+1$ can has no linear factors? Doesn't the condition expands to $a_n(1+\sum a_i) = 1(1+1) =1\cdot2 =2= 0\pmod 2$ ?

shouldn't it be "non-trivial linear factors"?

share|cite|improve this question
Well, in your example, you have $1(1+1) = 1\cdot 0 = 0$, but the condition says $a_n(1 + \sum a_i) \neq 0$. – Daniel Fischer Jul 27 '13 at 16:01
$x+1$ is itself a linear factor. – Kunnysan Jul 27 '13 at 16:01
@DanielFischer so the condition isn't satisfied but it has no linear factors, this is why I ask – where_is_tftp Jul 27 '13 at 16:09
The claim is that that polynomial has no linear factors if and only if $a_n(1 + \sum a_i) \neq 0$. In the case of $X+1$, $a_n(1 + \sum a_i) = 1(1+1) = 0$. So you should expect a linear factor. This linear factor is $X+1$. Where's the confusion? – Billy Jul 27 '13 at 16:28
(What is a "trivial" linear factor anyway? There are only two linear polynomials - $X$ and $X+1$ - and neither satisfies the condition $a_n(1 + \sum a_i) \neq 0$.) – Billy Jul 27 '13 at 16:28
up vote 2 down vote accepted

No, it shouldn't say "non-trivial." If $a_n=0$ then $X$ is a linear factor. If $a_0+\dots+a_n=0$ then $X+1$ is a linear factor.

If it said non-trivial, then the statement would no longer be true.

This theorem is stated badly, because it is of the form $\lnot P\iff\lnot Q$, which is always equivalent to $P\iff Q$.

In this case, you can state the theorem as:

Let $f(X)=X^n+\dots +a_n\in\mathbb Z_2[X]$. Then $f(X)$ has a linear factor if and only if $a_n(a_1+\dots+a_n)=0$.

If you stated instead:

Let $f(X)=X^n+\dots +a_n\in\mathbb Z_2[X]$. Then $f(X)$ has a non-trivial linear factor if and only if $a_n(a_0+\dots+a_n)=0$.

In this statement, $P$ is "$f(X)$ has a non-trivial linear factor" and $Q$ is "$a_n(a_0+\dots+a_n)=0$." With $f(X)=X+1$, $P$ is false and $Q$ is true, so $P\iff Q$ is not true.

So your example is exactly why the theorem doesn't have the added condition.

share|cite|improve this answer
$f(X)=0$ does not satisfy the above, as it's not in the form postulated in the hypothesis (there's no $X^n$ with coefficient $1$). Note that it requires that $a_0=1$. – tomasz Jul 27 '13 at 17:04
Oops, missed that, thanks. But the theorem extends to $f(X)=0$. :) @tomasz – Thomas Andrews Jul 27 '13 at 17:07
@ThomasAndrews I think you forgot 1 in condition with braces: sum(ai) should be 1+sum(ai) regarding my notation and yours to express f(X), is this correct? I assume you mean a0 stands for X^n coefficient and equals 0 but it isn't clear – where_is_tftp Oct 15 '13 at 22:48

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.