I am reading Geisel's tutorial$^{\color{red}{\star}}$ on Reed-Solomon codes, in which it is tested whether the polynomial $f(x) = x^4 + x + 1$ is irreducible. From pages 15 and 16,
As a first step, the polynomial $f(x) = x^4 + x + 1$ is evaluated at 0 (zero). The result is 1. The conclusion is 'Therefore, $(x + 0) = (x – 0)$ is not a factor (0 is not a root)'.
My questions are about this conclusion:
- How can $(x + 0) = (x – 0)$ be derived from the preceding text?
- What is meant by 'a factor' here? A reduced part of the polynomial?
- I understand that 0 (zero) is not a root, a root of a polynomial should result in 0 (zero) when evaluated. Why does this prove that $(x + 0) = (x – 0)$ is not a factor?
- Why does this conclusion eliminate one possible factor of the polynomial?
Hoping for someone patient to answer these questions.
$\color{red}{\star}$ William A. Geisel, Tutorial on Reed-Solomon Error Correction Coding [PDF], NASA Technical Memorandum 102162, NASA, August 1990.
Best Answer
To address your second and fourth bullet points, it is a general fact for a polynomial ring over a field, $F[x]$: If $p(x)\in F[x]$ have root $r$ show that $x-r$ is a factor of $p(x)$ The converse of that statement is easily seen to be true also.
To address your first and third bullet points (the same thing?) when you express a polynomial as the product of two other polynomials, each of the two may be called a factor.
Usually we're interested in the case when the factors have degree 1 or more, so that we've really decomposed the original polynomial into a product.
They repeat the same logic with $1$, demonstrating $(x-1)$ is not a factor off the polynomial either.
At the same time, this establishes the polynomial doesn't have a factor of degree 3 (because the other factor would have to be something like $(x-r)$, and you already eliminated that.)
To show that the polynomial is irreducible, there's only one more case to rule out: the possibility that it's a product of two polynomials of degree $2$.
PS also if it wasn't obvious, since you're working over $GF(2)$, you have that $p=-p$ for every polynomial... that is, addition and subtraction in this ring are the same thing. This explains the sign changes you were apparently asking about.