Cyclic codes: greatest common divisor of the generator polynomial and $x^n-1$

Question

Let's say I have the cyclic code $<z(x)>$ for some polynomial $z(x)$, and it's generator polynomial is $g(x)$. How can I prove that $g(x)$ is the greatest common divisor of $z(x)$ and of $x^n-1$?

Answer 1

Because the ring $\Bbb{F}_q[x]$ is a principal ideal domain, the ideal $I=\langle z(x), x^n-1\rangle$ is actually principal, and generated by $d(x)=\gcd(z(x),x^n-1)$. Furthermore, Euclid's algorithm for computing that gcd actually produces the lowest degree non-zero polynomial in $I$. You may have seen this result in the context of ideals of $\Bbb{Z}$. It is a part of Bezout's identity.

Anyway, when we view $I$ as a cyclic code, the lowest degree non-zero polynomial (unique up to a non-zero scalar factor so literally unique in the common case $q=2$) is the generator of the cyclic code. See e.g. chapter 7 of MacWilliams and Sloane. All this is kinda implicit in thar chapter and the following one.