= Solution
A binary <cyclic code> is a linear subspace of $\mathbb F_2^N$ invariant under cyclic coordinate shift. Associate a word $(c_0,\ldots,c_{N-1})$ to $\sum c_jX^j$ in $\mathbb F_2[X]/(X^N-1)$. Cyclic shift is multiplication by $X$, so linearity and shift invariance make the code an ideal of this quotient.
Its inverse image in $\mathbb F_2[X]$ is an ideal containing $(X^N-1)$. Since a <polynomial> ring over a field is a <principal ideal domain>, that inverse image is $(g)$ for a unique monic <polynomial> $g$. Containment gives $X^N-1=gh$ for some <polynomial> $h$. Thus the <generator polynomial of a cyclic code> satisfies
$$
\boxed{g\mid X^N-1,\qquad C=(g)\text{ modulo }X^N-1.}
$$
For a nonzero code $g$ is also its monic word <polynomial> of smallest degree. For the zero code use $g=X^N-1$, whose residue is zero. Conversely every monic divisor defines a <cyclic code>, proving the full correspondence.
Over $\mathbb F_2$,
$$
X^5-1=(X+1)(X^4+X^3+X^2+X+1).
$$
The quartic factor has no root in $\mathbb F_2$. The only monic irreducible quadratic over this field is $X^2+X+1$, and division leaves remainder $X+1$, so the quartic is not divisible by it. A reducible quartic with no linear factor would have two irreducible quadratic factors; hence this quartic is irreducible. There are exactly four <binary cyclic codes of length five>, given by the <generator polynomials of a cyclic code>
$$
\boxed{1,\quad X+1,\quad X^4+X^3+X^2+X+1,\quad X^5-1.}
$$
They are respectively the full space, the even-weight code, the repetition code and the zero code, with dimensions $5,4,1,0$.
Back to article page
