[proofplan] We represent every non-zero element of the quotient ring $\mathbb{F}_2[X]/(X^n - 1)$ by its unique polynomial representative of degree $< n$, and select $g$ to be a non-zero representative of minimum degree in $C$. Using polynomial division against $g$, we show that every element of $C$ is a multiple of $g$, giving $C \subseteq (g)$; the reverse inclusion is immediate from $g \in C$ and the ideal property. Applying the same division argument to the polynomial $X^n - 1$ (which represents $0 \in C$) yields $g \mid X^n - 1$. Uniqueness follows because over $\mathbb{F}_2[X]$, two monic polynomials that divide each other are equal. [/proofplan] [step:Choose $g$ as a non-zero representative of minimum degree in $C$] Every non-zero element of $\mathbb{F}_2[X]/(X^n - 1)$ is represented by a unique polynomial in $\mathbb{F}_2[X]$ of degree strictly less than $n$ (the representatives are exactly the remainders on division by $X^n - 1$, and division yields a unique remainder of degree $< \deg(X^n - 1) = n$). Because $C$ is a non-zero ideal, the set \begin{align*} S := \{ \deg p : 0 \neq p \in \mathbb{F}_2[X],\ \deg p < n,\ p \bmod (X^n - 1) \in C \} \end{align*} is a non-empty subset of $\{0, 1, \ldots, n-1\}$. By well-ordering of $\mathbb{N}$, $S$ has a minimum element $k$. Let $g \in \mathbb{F}_2[X]$ with $\deg g = k$ and $g \bmod (X^n - 1) \in C \setminus \{0\}$. Over $\mathbb{F}_2$, every non-zero polynomial has leading coefficient $1$ (the only non-zero scalar in $\mathbb{F}_2$), so $g$ is automatically monic. [/step] [step:Show $C = (g)$ via polynomial division with remainder] We prove $(g) \subseteq C$ and $C \subseteq (g)$. *Inclusion $(g) \subseteq C$.* By construction $g \bmod (X^n - 1) \in C$. Since $C$ is an ideal of $\mathbb{F}_2[X]/(X^n - 1)$, it absorbs multiplication: for every $f \in \mathbb{F}_2[X]$, the product $fg \bmod (X^n - 1)$ lies in $C$. Hence $(g) \subseteq C$. *Inclusion $C \subseteq (g)$.* Let $c \in C$ and let $p \in \mathbb{F}_2[X]$ be its unique representative of degree $< n$ (with $p = 0$ if $c = 0$). By polynomial division in $\mathbb{F}_2[X]$, which is a Euclidean domain, there exist unique $q, r \in \mathbb{F}_2[X]$ with \begin{align*} p(X) = q(X) g(X) + r(X), \qquad \deg r < \deg g = k \quad \text{or } r = 0. \end{align*} Reducing modulo $X^n - 1$: \begin{align*} r \bmod (X^n - 1) = \big(p - q g\big) \bmod (X^n - 1) = c - \underbrace{qg \bmod (X^n - 1)}_{\in\, C} \in C, \end{align*} because $C$ is closed under subtraction (it is an ideal, hence an additive subgroup) and under multiplication by $q$ (ideal absorption). Note also that $\deg r < k < n$, so $r$ is already its own reduction modulo $X^n - 1$. If $r \neq 0$, then $r$ is a non-zero representative in $C$ with $\deg r < k$, contradicting the minimality of $k$. Therefore $r = 0$, giving $p = qg$ and hence $c = p \bmod (X^n - 1) = qg \bmod (X^n - 1) \in (g)$. Thus $C \subseteq (g)$ and overall $C = (g)$, proving (1). [guided] The strategy is the standard "ideal-of-least-degree" argument that exhibits $\mathbb{F}_2[X]$ as a PID, adapted to the quotient ring $\mathbb{F}_2[X]/(X^n - 1)$. On the one hand, because $g$ lies in $C$ and $C$ is an ideal, every product $fg$ (mod $X^n - 1$) must also lie in $C$ — this gives $(g) \subseteq C$ for free. On the other hand, to show $C \subseteq (g)$, we pick an arbitrary codeword $c \in C$ with degree-$< n$ representative $p$, and we divide $p$ by $g$ using the Euclidean algorithm in $\mathbb{F}_2[X]$: \begin{align*} p(X) = q(X) g(X) + r(X), \qquad \deg r < \deg g \text{ or } r = 0. \end{align*} Why does this division exist? Because $\mathbb{F}_2[X]$ is a Euclidean domain — $g$ is monic (so its leading coefficient is invertible), and polynomial long division terminates. The key observation is that the remainder $r$ belongs to $C$: rearranging, \begin{align*} r = p - qg, \end{align*} and both $p$ (as $c$) and $qg \bmod (X^n - 1)$ lie in $C$ (the second by ideal absorption — $C$ is closed under multiplication by elements of the ambient ring). Since $C$ is closed under addition (it is an additive subgroup), their difference $r$ lies in $C$ as well. Also, $\deg r < \deg g < n$, so $r$ already represents itself in the quotient — no further reduction is needed. Now comes the contradiction. We chose $g$ to have **minimal** degree among non-zero representatives in $C$. If $r$ were non-zero, then $r$ would be a non-zero representative in $C$ with $\deg r < \deg g$, which is impossible. So $r = 0$, giving $p = qg$ and therefore $c = qg \bmod (X^n - 1) \in (g)$. Since $c \in C$ was arbitrary, $C \subseteq (g)$; combined with $(g) \subseteq C$, we conclude $C = (g)$. [/guided] [/step] [step:Apply the division argument to $X^n - 1$ to obtain $g \mid X^n - 1$] In the quotient $\mathbb{F}_2[X]/(X^n - 1)$, the element $X^n - 1$ reduces to $0 \in C$. Divide $X^n - 1$ by $g$ in $\mathbb{F}_2[X]$: \begin{align*} X^n - 1 = Q(X) g(X) + R(X), \qquad \deg R < \deg g = k \quad \text{or } R = 0. \end{align*} Reduce modulo $X^n - 1$: \begin{align*} R \bmod (X^n - 1) = \big((X^n - 1) - Qg\big) \bmod (X^n - 1) = 0 - Qg \bmod (X^n - 1) \in C, \end{align*} since $Qg \bmod (X^n - 1) \in C$ by the ideal property. Moreover $\deg R < k < n$ so $R$ equals its own reduction. If $R \neq 0$, this contradicts minimality of $k$. Therefore $R = 0$ and $g \mid X^n - 1$ in $\mathbb{F}_2[X]$, proving (2). [/step] [step:Derive the divisibility criterion for codewords] Let $p \in \mathbb{F}_2[X]$ with $\deg p < n$. We show that $p \bmod (X^n - 1) \in C$ if and only if $g \mid p$ in $\mathbb{F}_2[X]$. *($\Rightarrow$)* If $p \bmod (X^n - 1) \in C = (g)$, then $p \bmod (X^n - 1) = qg \bmod (X^n - 1)$ for some $q \in \mathbb{F}_2[X]$. The division argument from Step 2 applied to $p$ shows that the polynomial remainder when dividing $p$ by $g$ is $0$, i.e., $g \mid p$. *($\Leftarrow$)* If $g \mid p$, write $p = fg$ for some $f \in \mathbb{F}_2[X]$. Then $p \bmod (X^n - 1) = fg \bmod (X^n - 1) \in (g) = C$. [/step] [step:Establish uniqueness of $g$] Suppose $g_1, g_2 \in \mathbb{F}_2[X]$ are monic, each of degree $< n$, each generating $C$ as in (1), and each dividing $X^n - 1$ as in (2). Since $C = (g_1) = (g_2)$: - $g_2 \bmod (X^n - 1) \in (g_1)$, so by the divisibility criterion in Step 4, $g_1 \mid g_2$ in $\mathbb{F}_2[X]$. - $g_1 \bmod (X^n - 1) \in (g_2)$, so by the same criterion, $g_2 \mid g_1$ in $\mathbb{F}_2[X]$. Two non-zero polynomials $g_1, g_2 \in \mathbb{F}_2[X]$ with $g_1 \mid g_2$ and $g_2 \mid g_1$ are associates: $g_1 = u g_2$ for some unit $u \in \mathbb{F}_2[X]^\times = \mathbb{F}_2^\times = \{1\}$. Therefore $u = 1$ and $g_1 = g_2$. Combining Steps 1–5, there exists a unique monic polynomial $g \in \mathbb{F}_2[X]$ of degree $< n$ with $C = (g)$ and $g \mid X^n - 1$, and the codeword membership criterion $g \mid p$ holds. This completes the proof. [/step]