Find the minimal $n$ for there exists $[n,n-5]$ cyclic binary code with generator polynomial $g(x)=1+x^4+x^5$.
I couldn't figure out the answer. The only way I could think of is find out all the factorizations for $x^n-1$ for each $n>5$, but it is really hard work and I don't think this is what I should do. I am learning with Raymond Hill's book A First Course in Coding Theory and I couldn't find any theorem that will help me figure it out.
Thanks.
On
Hint: You can factor $$ \begin{aligned} g(x)=(x^5+x^4+x^3)+(x^3+1)&=x^3(x^2+x+1)+(x+1)(x^2+x+1)\\ &=(x^3+x+1)(x^2+x+1). \end{aligned} $$ I hazard a guess that the same exercise has been solved as an example for both these factors. If not you can handle the factors separately using Leox' (+1) method. These irreducible factor yield smaller values for $n$. As they are coprime you can take advantage. After all $g(x)\mid x^n-1$ iff both factors do. Remember that $x^n-1\mid x^m-1$ iff $n\mid m$.
On
The factorization of $g$ into irreducibles is $$1 + x^4 + x^5 = (x^2 + x + 1)(x^3 + x + 1).$$
Let $a$ be a zero of $x^2 + x + 1$. Since $x^2 + x + 1$ is irreducible, $[\mathbb F_2(a) : \mathbb F_2] = \operatorname{deg}(x^2 + x = 1) = 2$, so $\mathbb F_2(a) = \mathbb F_4$ and $a\in \mathbb F_4^\times$. Because $\lvert \mathbb F_4\rvert ^\times = 3$ is prime, we get the multiplicative order of $a$ as $3$ ($1$ is not possible since $a\neq 1$).
Similarly, all zeros of $x^3 + x + 1$ have multiplicative order $7$.
Your are looking for the smallest $n\geq 1$ with $g\mid x^n - 1$. Equivalently, $n$ is the smallest number with $z^n = 1$ for all zeros of $g$ (here we use that $g$ has no repeated roots). Hence $$n = \operatorname{lcm}(3,7) = 21.$$
Let $\alpha$ be a root of $g(x).$ Then we have that $\alpha^5=\alpha^4+1$. ( We works in $\mathbb{Z}_2$) Therefore we get $$ \begin{gather*} \alpha^6=\alpha^5+\alpha=\alpha^4+\alpha+1,\\ \alpha^7=\alpha^5+\alpha^2+\alpha=\alpha^4+\alpha^2+\alpha+1,\\ \ldots \end{gather*} $$ and so on untill you will obtain $\alpha^n=1$ for some $n.$ Then $n$ is the codelenght of the cyclic code.