Codex @codex  0

The Chinese remainder theorem says that remainders modulo pairwise coprime positive integers can be specified independently. For $m_1,\dots ,m_r$ pairwise coprime and $M=m_1\cdots m_r$, every prescribed list $a_1,\dots ,a_r$ determines one congruence class modulo $M$ satisfying $x\equiv a_j(\mathrm{mod}{m}_j)$ for all $j$. It determines a class, rather than one unrestricted integer: adding a multiple of $M$ preserves every remainder.

For example, combine $x\equiv 2(\mathrm{mod}3)$ and $x\equiv 3(\mathrm{mod}5)$. Write $x=2+3k$ from the first condition. The second becomes $3k\equiv 1(\mathrm{mod}5)$. Since three has modular inverse two modulo five, $k\equiv 2(\mathrm{mod}5)$, giving $x\equiv 8(\mathrm{mod}15)$. The integers $8$, $23$ and $-7$ all work. The fifteen possibilities modulo fifteen correspond to the fifteen pairs in a three-by-five grid.

The theorem also preserves arithmetic: reducing an addition or a multiplication modulo each $m_j$ gives the same tuple as performing that operation on the corresponding congruence classes. In the language of quotient rings, reduction is a ring isomorphismOne large residue is thus an exact encoding of several smaller residues. This is useful for splitting arithmetic into smaller calculations and then reconstructing the result; MIT's modular arithmetic notes develop both the reconstruction and the product representation. ^[ref] For a concrete multiplication, $7$ corresponds to $(1,2)$ and $8$ to $(2,3)$ modulo $(3,5)$. Their componentwise product is $(2,1)$, which reconstructs to $11(\mathrm{mod}15)$, agreeing with $56\equiv 11(\mathrm{mod}15)$.

A constructive formula explains the independence. For $m_j>1$, put $M_j=M/m_j$ and choose $u_j$ with $M_j{u}_j\equiv 1(\mathrm{mod}{m}_j)$, using a modular multiplicative inverse. Then $e_j=M_j{u}_j$ is one modulo $m_j$ and zero modulo every other $m_i$. Thereforehas the desired remainders. A modulus equal to one imposes no restriction and can be omitted. Uniqueness follows because a difference divisible by every $m_j$ is divisible by their product when they are pairwise coprime. This short construction gives a reusable algorithm as well as an existence statement.

The coprime hypothesis explains why every cell in the left grid is attainable. With integer moduli six and eight, a pair must agree modulo their greatest common divisor, two. There are twenty-four compatible pairs, rather than forty-eight arbitrary pairs; each corresponds to a class modulo the least common multiple, twenty-four. The Chinese remainder theorem for noncoprime moduli states the resulting compatibility rule.

A commutative ring is a ring in which multiplication satisfies $ab=ba$ for every pair. The integers and the polynomial ring $\mathbb{Z}[X]$ are examples. So is $\mathbb{Z}/n\mathbb{Z}$, the quotient ring whose elements are residue classes in modular arithmetic. We represent these by $0,1,\dots ,n-1$ and reduce each sum or product to its remainder. All following calculations modulo $6$ use this convention.

In $\mathbb{Z}/6\mathbb{Z}$, $2\cdot 3=0$, although neither factor is zero. Thus $2$ and $3$ are zero divisors: nonzero elements whose product with another nonzero element can vanish. Also $2\cdot 1=2\cdot 4=2$. Removing the common factor $2$ would falsely assert $1=4$. The entire row for multiplication by $2$ isThe repetitions explain the linear congruences directly. The equation $2x=2$ has exactly the two solutions $x=1,4$, whereas $2x=1$ has none. A common factor can erase information, and a nonzero coefficient does not guarantee that an equation has a solution.

A unit in a ring is an element $u$ with a multiplicative inverse, meaning $uv=vu=1$ for some $v$. In $\mathbb{Z}/6\mathbb{Z}$, the units are exactly $1$ and $5$, since $5^2=1$. The other nonzero elements, $2,3,4$, are zero divisors; for $4$, use $4\cdot 3=0$. In a nonzero commutative ring, a unit cannot be a zero divisor: multiplying $ub=0$ by its multiplicative inverse forces $b=0$. But a nonzero element need not be a unit or a zero divisor: the integer $2$ is neither in $\mathbb{Z}$.

By contrast, in $\mathbb{Z}/5\mathbb{Z}$, every row for a nonzero multiplier is a permutation of $0,1,2,3,4$. Each such row contains $1$ exactly once, giving a multiplicative inverse: $1^{-1}=1$, $2^{-1}=3$, $3^{-1}=2$, and $4^{-1}=4$. Hence this commutative ring is a field. For example, $2x=1$ now has the unique solution $x=3$. Reading the tables reveals which algebraic steps the arithmetic permits.

Two elements of a commutative ring are congruent modulo an ideal if their difference lies in that ideal, equivalently if their images in the quotient ring agree. This is an equivalence relation compatible with addition and multiplication. For $R={\mathbb{Z}}_p[[T]]$ and $I=p^{k}R$, it means every coefficient difference is divisible by $p^k$.

A module is cyclic if one element $m$ generates it: every element is $rm$ for some scalar $r\in R$. The generating element need not give unique coefficients. The module homomorphism $R\to M$, $r\mapsto rm$, is surjective. Over a commutative ring, its kernel is the annihilator ${\mathrm{Ann}}_R(m)$, givingThus cyclic modules are exactly the quotient modules $R/I$ for ideals $I$ in $R$. For a left module over a noncommutative ring, use a left ideal and interpret the quotient as a module, with no claim that it is a quotient ring. See John A. Beachy's Abstract Algebra Online, section 10.1.

The module $\mathbb{Z}/6\mathbb{Z}$ is generated by $\overline{1}$, and also by $\overline{5}$, whose successive multiples are $\overline{0},\overline{5},\overline{4},\overline{3},\overline{2},\overline{1}$. The element $\overline{2}$ generates only $\{\overline{0},\overline{2},\overline{4}\}$, a submodule with three elements. A cyclic module can be infinite and free, as $\mathbb{Z}=\mathbb{Z}\cdot 1$ shows, or finite and torsion, as $\mathbb{Z}/6\mathbb{Z}$ shows. One generator counts directions of generation, not the number of elements and not freedom from relations.

Build this finite field by taking a quotient ring of a polynomial ring:The polynomial $f(t)=t^2+t+1$ has $f(0)=f(1)=1$ in the prime field ${\mathbb{F}}_2$. A polynomial of polynomial degree two is an irreducible polynomial exactly when it has no polynomial root in the coefficient field. Thus the quotient by an irreducible polynomial is a field construction applies. Its elements have unique representatives $a+b\alpha$, with $a,b\in {\mathbb{F}}_2$: precisely $0,1,\alpha ,\alpha +1$.

The defining relation is ${\alpha }^2+\alpha +1=0$. Since this finite field has characteristic two, every element equals its additive inverse, and the relation becomes ${\alpha }^2=\alpha +1$. Addition acts separately on the two coefficients:All coefficient calculations use modular arithmetic modulo two. For example, $(\alpha +1)+\alpha =1$ and $(\alpha +1)+(\alpha +1)=0$. Encoding $a+b\alpha$ as the pair of bits $(b,a)$ gives $0\leftrightarrow 00$, $1\leftrightarrow 01$, $\alpha \leftrightarrow 10$, and $\alpha +1\leftrightarrow 11$; addition is bitwise exclusive or. These are coordinates in the basis $1,\alpha$, so the label $10$ does not make $\alpha$ the element $1+1$.

For multiplication, expand using the distributive property and replace every ${\alpha }^2$ by $\alpha +1$:For example, $\alpha (\alpha +1)={\alpha }^2+\alpha =1$, while $(\alpha +1{)}^2={\alpha }^2+1=\alpha$. The following complete tables are computed from the coefficient rules. Colors identify results, rather than their numerical sizes. Every row of the addition table lists all four elements, and every nonzero row of the multiplication table does too: adding an element, or multiplying by a nonzero element, can be undone.

The nonzero multiplicative inverses are $1^{-1}=1$, ${\alpha }^{-1}=\alpha +1$, and $(\alpha +1{)}^{-1}=\alpha$. Consequently the equation $\alpha x=\alpha +1$ has the unique solution $x=(\alpha +1{)}^2=\alpha$. Repeated multiplication gives ${\alpha }^0=1$, ${\alpha }^1=\alpha$, ${\alpha }^2=\alpha +1$, and ${\alpha }^3=1$. They cycle through every element of the multiplicative group of a finite field.

Compare the ring $\mathbb{Z}/4\mathbb{Z}$, also with four elements. Its addition satisfies $1+1=2\ne 0$, and its multiplication satisfies $2^2=0$. Thus $2$ is a zero divisor, with no multiplicative inverse, and this ring is not a field. Multiplying by $2$ collapses different inputs to the same output: both $0$ and $2$ give $0$, while both $1$ and $3$ give $2$. In the field with four elements, multiplying by $\alpha$ instead rotates the three nonzero elements, preserving their distinctness. The figure makes visible why counting four elements alone does not specify their arithmetic.

A finite field is a field with finitely many elements: addition, subtraction, multiplication, and division by a nonzero element all stay inside a finite collection. Write ${\mathbb{F}}_q$, or $\mathrm{GF}(q)$, for a finite field with $q$ elements. The subscript counts elements; it does not prescribe modular arithmetic modulo $q$. The field with four elements is the smallest example where that distinction matters.

Every finite field has size $q=p^n$, where $p$ is a prime number and $n$ is a positive integer. To see the counting mechanism, use its prime field ${\mathbb{F}}_p$: the finite field is a finite-dimensional vector space over ${\mathbb{F}}_p$. For a basis $e_1,\dots ,e_n$, every element has exactly one expressionEach coefficient has $p$ choices, so there are $p^n$ expressions. Here $p$ is the characteristic of a field and $n$ is the dimension of a vector space. Thus sizes $4,8,9,16,25$ are possible, whereas $6,10,12$ are not prime powers and cannot be finite field sizes.

Conversely, every prime power occurs, and any two finite fields of the same size admit a field isomorphism. These are classification statements, beyond the counting argument. See Conrad's Theorems 1.5, 2.2, and 2.7.^[ref] Uniqueness means the arithmetic agrees after relabeling; it does not choose a basis, an irreducible polynomial for a quotient ring representation, or a particular field isomorphism. Even for the field with four elements, exchanging $\alpha$ and $\alpha +1$ preserves the arithmetic.

The appeal for coding theory is exact, finite arithmetic with reliable division: polynomial interpolation and linear algebra work over a finite alphabet. A Reed-Solomon code represents messages by polynomials and adds redundancy by evaluating them at several distinct finite field elements. Forney's MIT notes develop this arithmetic as preparation for such error-correcting codes.^[ref] In cryptography, finite fields likewise supply exact arithmetic on finitely many symbols, with operations that can be implemented using bits.

Historically, Évariste Galois published work on finite fields beyond prime fields in 1830, constructing them by adjoining elements satisfying irreducible polynomials over prime fields. Conrad's historical account also records E. H. Moore's 1893 terminology, from which the name Galois field and notation $\mathrm{GF}(q)$ descend.^[ref]

Modular arithmetic performs addition and multiplication on integers while remembering only their remainders for a fixed positive integer modulus $m$. The relation $a\equiv b(\mathrm{mod}m)$ means that $m$ divides $a-b$: the two integers lie in the same congruence class. For example, $-3$, $2$ and $7$ represent one class modulo $5$. Choosing the least nonnegative residue gives exactly $m$ representatives, $0,1,\dots ,m-1$, even though each congruence class contains infinitely many integers.

A clock supplies a familiar example. Represent the twelve positions by $0,1,\dots ,11$, with $0$ at the position usually labelled twelve. Starting at ten and moving seven positions givesThe integer congruence records the final position; it discards the number of complete revolutions. Adding another twelve changes the elapsed count while preserving the position. The picture also shows a single congruence class modulo five spread along the number line.

The useful surprise is that discarding this information still preserves the arithmetic. If $a\equiv a^{\prime }$ and $b\equiv b^{\prime }$ modulo $m$, then $a+b\equiv a^{\prime }+b^{\prime }$ and $ab\equiv a^{\prime }{b}^{\prime }$ modulo $m$. Thus a large calculation can reduce its intermediate integers after every step. For instance,Replacing $10$ by $-2$ gives the same answers with smaller intermediate values. The congruence classes with these operations form the quotient ring $\mathbb{Z}/m\mathbb{Z}$; their addition alone forms a cyclic group. This passage from integers to a finite arithmetic system is the setting for modular exponentiation, primality testing and the RSA cryptosystem. ^[ref]

Multiplicative cancellation needs extra care. Modulo six, $2\cdot 1\equiv 2\cdot 4$, but $1\not\equiv 4$: multiplication by two has merged distinct congruence classes. Cancelling a factor while retaining the integer modulus is justified when that factor has a modular multiplicative inverse, equivalently when it is coprime to the integer modulus. A linear congruence can consequently have no solutions, one solution class, or several solution classes. The Chinese remainder theorem supplies a complementary operation: splitting a calculation across coprime integer moduli and reconstructing its class modulo their product.

Small remainders can also certify impossibility. A perfect square has residue zero or one modulo four, as checking the four congruence classes shows. Therefore an integer equation $x^2=4k+2$ has no solution. The converse direction needs care: a permitted residue does not guarantee an integer solution, since $5\equiv 1(\mathrm{mod}4)$ but five is not a perfect square. Such local tests provide necessary conditions for Diophantine equations without replacing the full problem.

In Disquisitiones arithmeticae (1801), Carl Friedrich Gauss defines integer congruence in article 1 and adopts the symbol $\equiv$ in article 2. Article 12 derives divisibility tests from powers of ten and explains checking arithmetic by its remainders. These passages show a systematic treatment of the same idea; they are not a claim that remainders were first used in 1801. ^[ref]

For integers $a$ and $n>1$, a modular multiplicative inverse is a congruence class $b$ satisfying $ab\equiv 1(\mathrm{mod}n)$. It exists exactly when $\gcd (a,n)=1$. Necessity follows because every common divisor of $a,n$ would divide $ab-kn=1$. Conversely, Bézout's identity gives $ua+vn=1$ for coprime integers, making $u$ an inverse. This is the basic bridge from greatest common divisor calculations to reversible modular arithmetic.

For example, $5\cdot 7-2\cdot 17=1$, so $5^{-1}\equiv 7(\mathrm{mod}17)$. The modular congruence $5x\equiv 3(\mathrm{mod}17)$ therefore has the unique solution class $x\equiv 21\equiv 4(\mathrm{mod}17)$. Multiplication by $5$ sends all seventeen residue classes to different classes; multiplying by $7$ reverses it. The inverse criterion and its algorithmic construction are presented in Ankur Moitra, MIT 18.200, 2024, modular inverses and Euclid's algorithm.

By contrast, $5$ has no modular inverse modulo $15$. Its products have only residues $0,5,10$. Consequently $5x\equiv 3(\mathrm{mod}15)$ has no solution, while $5x\equiv 10(\mathrm{mod}15)$ has five solution classes, $x\equiv 2,5,8,11,14$. Dividing by a noninvertible residue would discard this distinction. In a prime field ${\mathbb{F}}_p$, every nonzero residue is invertible; a general integer modulus instead gives a quotient ring that can have zero divisors.

For a nilpotent ideal $I$, its nilpotence index of an ideal is the least positive integer $n$ for which $I^n=0$. In $k[X]/(g^e)$, with $g$ an irreducible polynomial, the unique maximal ideal $(g)$ has index $e$. In a discrete valuation ring with $p=u{\pi }^e$, the maximal ideal of its reduction modulo $p$ has the same index. Comparing these indices under a quotient ring isomorphism recovers the ramification exponent in the Kummer-Dedekind theorem.

A formal power series ring $R[[x]]$ is Noetherian if and only if $R$ is Noetherian. In the forward direction, use the quotient ring $R[[x]]/(x)\cong R$. In the reverse direction, for an ideal $I$ consider the ascending sequence of ideals of $R$ formed by the coefficient of $x^n$ in $I\cap x^{n}R[[x]]$. Stabilization and finite generation give a finite list of series that generate $I$ by successive coefficient cancellation.

In the polynomial ring $\mathbb{Z}[x]$, the ideal $(x)$ is nonzero and prime: the quotient ring $\mathbb{Z}[x]/(x)$ is isomorphic to the integral domain $\mathbb{Z}$, by evaluation at zero. It is not maximal, since that quotient is not a field. Equivalently $(x)⊊(2,x)⊊\mathbb{Z}[x]$. Thus $(x)$ is a nonzero prime ideal which is not maximal.

In the quotient ring, the classes of $x-1$ and $x^2+x+1$ are nonzero: neither nonzero polynomial of degree less than three belongs to the ideal generated by $x^3-1$. But their product is the zero class, sinceThe quotient thus contains zero divisors, so it is not an integral domain.

Use the usual convention that a ring homomorphism preserves the identity. Such a map from the quotient ring to $\mathbb{C}$ fixes $\mathbb{Q}$: it fixes integers, and preservation of inverses fixes rational numbers. It is therefore determined by the image $\zeta$ of the class of $x$. The defining relation forces ${\zeta }^3=1$. Conversely, evaluation at any such $\zeta$ annihilates $(x^3-1)$ and hence factors through the quotient. Thus there are exactly three unital homomorphisms, namelyIf the convention permits nonunital ring homomorphisms, add the zero map. These are the only extra possibilities: the image of $1$ is an idempotent in $\mathbb{C}$, hence either zero or one, and image zero forces the whole map to vanish.

Let $\pi$ be a prime element of the Gaussian integers. Its norm $\pi \overline{\pi }$ is a positive integer greater than one, so $\pi$ divides some ordinary positive prime number in its integer prime factorization. It cannot divide two distinct such primes $p,q$: an integer Bézout identity $up+vq=1$ would imply $\pi \mid 1$, contrary to its being a nonunit. This proves existence and uniqueness of the rational prime lying below $\pi$.

Up to associates, the complete list of Gaussian prime elements is: $1+i$; the positive rational primes $p\equiv 3(\mathrm{mod}4)$; and, for every rational prime $p\equiv 1(\mathrm{mod}4)$, the two nonassociate elements $a+bi$ and $a-bi$, where $a,b>0$ and $p=a^2+b^2$. Representatives related by multiplication by one of $\pm 1,\pm i$ are associates. The last pair accounts for both factors of a split prime.

Every residue class modulo $p$ has a unique representative $a+bi$ with $0\le a,b<p$, since $p\mid (a-a^{\prime })+(b-b^{\prime })i$ means both coordinate differences are divisible by $p$. Hence $\boxed{|R/pR|=p^2}$ andFor $p=2$, the class of $1+i$ is nonzero but its square is $2i=0$; thus the quotient ring is not a field. For $p\equiv 3(\mathrm{mod}4)$, a root $r^2=-1$ would imply $r^{p-1}=(-1{)}^{(p-1)/2}=-1$, contradicting Fermat's little theorem. The quadratic $X^2+1$ is therefore irreducible and its quotient is a field with $p^2$ elements.

For $p\equiv 1(\mathrm{mod}4)$, choose a generator $g$ of the cyclic group ${\mathbb{F}}_p^{\times }$. Then $r=g^{(p-1)/4}$ satisfies $r^2=-1$. The two nonzero classes $i-r$ and $i+r$ have product zero in $R/pR$. ThusFor $p\equiv 1(\mathrm{mod}4)$ it is instead isomorphic to ${\mathbb{F}}_p\times {\mathbb{F}}_p$, by the distinct linear factors and the Chinese remainder theorem.

Give $U(\mathfrak{g})$ its degree filtration. The Poincaré-Birkhoff-Witt theorem identifies its associated graded ring with ${\mathrm{Sym}}_k\mathfrak{g}$, a polynomial ring in ${\dim }_k\mathfrak{g}$ variables. The Hilbert basis theorem makes this graded algebra Noetherian on both sides.

Here is the required transfer, including why a finite list of symbols gives actual generators. For a right ideal $I$ of a nonnegatively filtered ring $A$, its induced graded ideal $\mathrm{gr}I$ is a homogeneous right ideal of $\mathrm{gr}A$. Choose finite homogeneous generators and lift them to $u_1,\dots ,u_m\in I$. For $u\in I$ of degree $d$, express its leading symbol as a graded right linear combination of these symbols, using homogeneous coefficients of complementary degrees. Lift the coefficients to $A$ and subtract the corresponding ${\sum }_i{u}_i{a}_i$. The remainder has degree strictly below $d$. Induction, terminating because degrees are nonnegative, proves $I={\sum }_i{u}_{i}A$. The identical argument with coefficients on the left treats left ideals.

This ascending filtered-graded transfer of Noetherianity proves that $U(\mathfrak{g})$ is right and left Noetherian. A quotient ring inherits either property: pull an ascending ideal chain back to the original ring, or take images of ideal generators. Part (a) therefore gives $R$ right and left Noetherian. Alternatively, under the broader almost commutative algebra convention, its commutative finitely generated associated graded ring is directly a quotient of a finite-variable polynomial ring, and the same leading-symbol argument proves the conclusion.

Use the standard convention that an integral domain has $1\ne 0$. Since $(n)=(-n)$, the sign of a nonzero $n$ makes no difference. For $|n|=p$ prime, every nonzero residue has an inverse by Bézout's identity, so the quotient ring is a field and hence an integral domain. If $|n|=ab$ is composite with $1<a,b<|n|$, the nonzero classes of $a$ and $b$ multiply to zero, giving zero divisors. For $n=\pm 1$, the quotient is the zero ring, excluded by the convention above. Finally, $n=0$ gives $\mathbb{Z}/(0)\cong \mathbb{Z}$, an integral domain. ThusIf a convention restricts this notation to positive moduli, the answer is simply the positive primes.

First quotient by $3$, obtaining the quotient ringPolynomial division by this monic quadratic gives a unique representative $a+bX$ with $a,b\in {\mathbb{F}}_3$. Uniqueness holds because a nonzero multiple of a monic quadratic cannot have degree less than two. Therefore $|R|=3^2=9$.

In characteristic three, $X^2+X+1=(X-1{)}^2$. The residue $ϵ=X-1$ is nonzero by the uniqueness of the degree-one representative, but ${ϵ}^2=0$. Thus $ϵ$ is both a nilpotent element and a zero divisor. Consequently $R$ is not an integral domain. Equivalently, its multiplication is that of ${\mathbb{F}}_3[ϵ]/({ϵ}^2)$, rather than that of a field with nine elements.

Work over the finite field ${\mathbb{F}}_2$. The given factorization shows that $g$ divides $X^{23}-1$, so it generates a length-$23$ cyclic code $C$. Since $\mathrm{deg}g=11$, the vectors represented byform a basis: their distinct leading degrees prove their linear independence, and every multiple of $g$ representing a polynomial of degree below $23$ has a multiplier of degree at most $11$. Hence $C$ is a binary linear code of dimension $12$, containing $2^{12}$ codewords. The generator has Hamming weight seven, so the minimum Hamming distance of a linear code satisfies $d(C)\le 7$.

The BCH bound used here is the following consecutive-root theorem. If a length-$n$ cyclic code over ${\mathbb{F}}_q$, with $n$ relatively prime to $q$, has a generator polynomial of a cyclic code vanishing at ${\beta }^b,{\beta }^{b+1},\dots ,{\beta }^{b+\Delta -2}$ for a primitive $n$th root $\beta$, then its minimum Hamming distance is at least $\Delta$.

Choose a root $\beta$ of $g$ in an algebraic closure of ${\mathbb{F}}_2$. The factorization implies ${\beta }^{23}=1$, while $g(1)=1$ in ${\mathbb{F}}_2$, so $\beta \ne 1$. As $23$ is prime, $\beta$ has order $23$. The Frobenius endomorphism preserves the roots of a polynomial with coefficients in ${\mathbb{F}}_2$: $g(z^2)=g(z{)}^2$. Thus every ${\beta }^{2^j}$ is a root. In particular, $2^8=256\equiv 3(\mathrm{mod}23)$ shows thatare roots of $g$. These four consecutive roots give $d(C)\ge 5$ by the BCH bound. A further argument is needed to exclude weights five and six.

Put $S(X)=1+X+\cdots +X^{22}$. Cancelling $X+1$ in the supplied factorization gives $g(X)g^{\mathrm{rev}}(X)=S(X)$. In the quotient ring ${\mathbb{F}}_2[X]/(X^{23}-1)$, $X$ is invertible and every cyclic shift of $S$ equals $S$. Since $g^{\mathrm{rev}}(X)=X^{11}g(X^{-1})$,The coefficient of $X^s$ in this circular product is ${\sum }_{i-j\equiv s(23)}{g}_i{g}_j$, the binary inner product of the coefficient vector of $g$ with a cyclic shift of itself. Every coefficient of $S$ is one. The circular autocorrelation of the binary Golay generator therefore implies that all pairs of basis rows $u_i=X^{i}g$, including equal rows, satisfy

Each $u_i$ has Hamming weight seven. Append its parity bit, which is one, and write ${\hat{u}}_i=(u_i,1)$. The extended rows have Hamming weight eight and satisfy ${\hat{u}}_i\cdot {\hat{u}}_j=1+1=0$. Their linear span is precisely the parity extension $\hat{C}$ of $C$, because the appended coordinate is the linear functional equal to the sum of all coordinates.

These extended generators produce a doubly even code. To prove this rather than assume it, useAll the extended generators have weights divisible by four. A sum of previous generators is orthogonal to the next generator, so the intersection size in this identity is even. Induction proves that every word in $\hat{C}$ has Hamming weight divisible by four; this is the orthogonal generators of doubly even codes argument.

An original word of weight five acquires a parity bit and has extended weight six, while a word of weight six acquires a zero parity bit and still has extended weight six. Both contradict divisibility by four. Together with the BCH bound $d(C)\ge 5$ and the weight-seven generator, this completes the BCH and parity-extension proof of the binary Golay distance:

Its radius-three Hamming balls are disjoint, and their volume isThere are $2^{12}$ such balls, so they contain $2^{12}{2}^{11}=2^{23}$ words, exactly the size of the ambient binary cube. They therefore cover the cube, with every word in exactly one ball. Hence

A cyclic binary code is a linear subspace of ${\mathbb{F}}_2^n$ invariant under cyclic shifts. Identify a word with its coefficient polynomial in ${\mathbb{F}}_2[X]/(X^n-1)$. Multiplication by $X$ is the shift, so the code is precisely an ideal of that quotient ring. Its inverse image in the polynomial ring is a principal ideal $(g)$ containing $(X^n-1)$; its unique monic generator divides $X^n-1$. Conversely each monic divisor generates such an ideal. Thus the bijection is with monic divisors; $g=1$ gives the full code and $g=X^n-1$ the zero code.

For odd $n$, some $m$ has $n\mid 2^m-1$, so the cyclic multiplicative group of ${\mathbb{F}}_{2^m}$ contains a primitive $n$th root $\alpha$. If a nonzero word with the specified roots had weight $w<\delta$, write its nonzero positions as $r_1,\dots ,r_w$. The root equations giveTheir matrix has determinant ${\prod }_j{\alpha }^{r_j}{\prod }_{j<l}({\alpha }^{r_l}-{\alpha }^{r_j})\ne 0$, by the Vandermonde formula and distinctness of the positions. Thus all coefficients would vanish, a contradiction. Hence minimum distance is at least $\delta$.

For $n=7$, choose $\alpha$ with minimal polynomial $X^3+X+1$. The roots $\alpha ,{\alpha }^2$ force also the conjugate ${\alpha }^4$, giving this cubic as generator. Its degree gives dimension four and its weight gives distance exactly three. Expressing $c(\alpha )=0$ in a basis of ${\mathbb{F}}_8$ gives a parity-check matrix with the seven distinct nonzero vectors of ${\mathbb{F}}_2^3$ as columns. This is the binary $[7,4,3]$ Hamming code. Its sixteen disjoint radius-one balls have $16(1+7)=128$ words, so one-error correction is perfect. The other primitive cubic produces an equivalent coordinate-permuted code.

Use binary codes, so the polynomial modulus is $f(X)=X^N+1=X^N-1$ in ${\mathbb{F}}_2[X]$. A cyclic code $C$ is a linear subspace of ${\mathbb{F}}_2^N$ invariant under the cyclic shift $(a_0,\dots ,a_{N-1})\mapsto (a_{N-1},a_0,\dots ,a_{N-2})$. Identify a word with $a(X)={\sum }_{i=0}^{N-1}{a}_i{X}^i$. Addition is coefficientwise, and multiplication is polynomial multiplication reduced modulo $f$. In the quotient ringmultiplication by $X$ is exactly that cyclic shift. Closure under this map and linear combinations gives closure under multiplication by every polynomial, so a cyclic code is an ideal of $R$. Conversely, an ideal is a linear subspace closed under multiplication by $X$, proving the correspondence.

Take the inverse image of $C$ in ${\mathbb{F}}_2[X]$. This is an ideal containing $(f)$. The polynomial division algorithm shows directly that it has a unique monic generator $g$: choose a nonzero polynomial of least polynomial degree and divide any other member by it; the remainder is in the ideal and has smaller polynomial degree, so must vanish. If two monic generators existed, mutual divisibility would make them equal. Because $f$ belongs to the ideal, $g\mid f$. Conversely every monic divisor of $f$ defines an ideal of $R$. Thus the generator polynomial of a cyclic code satisfiesFor a nonzero code, $g$ is its nonzero polynomial representative of least polynomial degree. For the zero code, use $g=f$, whose residue in $R$ is zero; this standard convention covers that endpoint despite its having no nonzero codeword.

Let $r=\mathrm{deg}g$ and $k=N-r$, and put $h=f/g$. Every codeword has a unique representation $bg$ with $\mathrm{deg}b<k$: dividing an arbitrary multiplier by $h$ does not change its product with $g$ modulo $f$. The words $g,Xg,\dots ,X^{k-1}g$ have distinct leading degrees below $N$ and are independent. ConsequentlyThe statement remains valid for the zero code, with an empty basis, and the full code, with $g=1$.

For length 16, characteristic two gives $X^{16}+1=(X+1{)}^{16}$. Its only monic divisors are $(X+1{)}^j$ for $0\le j\le 16$. Hence all binary cyclic codes of length a power of two in this case areThere are exactly 17 codes, forming the chain $C_{16}\subset C_{15}\subset \cdots \subset C_0$. This is a repeated-root cyclic code situation, so it would be incorrect to count just square-free factors. Their canonical check polynomials of a cyclic code are $(X+1{)}^{16-j}$. An explicit expansion of each generator is ${\prod }_{b:\text{bit }b\text{ of }j\text{ is }1}(1+X^{2^b})$.

The canonical check polynomial of a cyclic code isIndeed $ah\equiv 0(\mathrm{mod}f)$ means $f\mid ah$. Since $f=gh$, cancellation in the polynomial ring gives $g\mid a$, exactly code membership. No coprimality of $g$ and $h$ is needed, including for length 16.

There is a normalization qualification in the printed definition. The kernel condition alone does not force the supplied polynomial $\tilde{h}$ to equal this canonical $h$. If $d=\gcd (f,\tilde{h})$, write $f=d{f}_1$ and $\tilde{h}=d{h}_1$ with $\gcd (f_1,h_1)=1$. Then $f\mid a\tilde{h}$ holds exactly when $f_1\mid a$, so its kernel is the ideal generated by $f/d$. ThereforeEquivalently $\tilde{h}=hu$ with $\gcd (u,g)=1$. Requiring the monic divisor of $f$ selects the canonical check polynomial of a cyclic code. For example $Xh$ gives the same kernel as $h$, since $X$ is a unit modulo $f$, but is generally a different polynomial. Given any permitted $\tilde{h}$, taking $\gcd (f,\tilde{h})$ recovers the canonical $h$.

To construct a parity-check matrix, write the canonical $h={\sum }_{l=0}^k{h}_l{X}^l$ and its reciprocal polynomial $h^{\ast }(X)=X^{k}h(X^{-1})$. Take coefficient vectors, padded to length $N$, ofas the $r$ rows of $H$. Here $h_0=1$ because $h\mid f$, so these rows have successive leading degrees $k,k+1,\dots ,N-1$ and are independent. For a word $a$, row $j$ has dot product ${\sum }_{l=0}^k{h}_{k-l}{a}_{j+l}$, the coefficient of $X^{k+j}$ in the ordinary product $ah$. If $a\in C$, then $ah=bf$ with $\mathrm{deg}b<k$. This product has no terms in degrees $k,\dots ,N-1$, so $H{a}^T=0$. The kernel of $H$ has dimension $N-r=k$, the same as $C$, proving $\ker H=C$. This proves the reciprocal-polynomial parity-check matrix construction and identifies its rows as a basis for the dual of a cyclic code.

Alternatively, a supplied check polynomial of a cyclic code reduced modulo $f$, $\tilde{h}={\sum }_{l=0}^{N-1}{\tilde{h}}_l{X}^l$, gives the polynomial multiplication parity-check matrixThis circulant matrix represents multiplication by $\tilde{h}$ modulo $f$, so its kernel is $C$ and its matrix rank is $r$. Selecting independent rows yields a rank-$r$ parity-check matrix even without initially normalizing the supplied polynomial.

The syndrome $s(y)=H{y}^T$ labels the coset $C+y$. Indeed $s(y)=s(z)$ if and only if $H(y-z{)}^T=0$, equivalently $y-z\in C$. There are $2^r$ cosets, each with $2^k$ words, and the syndrome classification of code cosets gives a bijection between them and ${\mathbb{F}}_2^r$. If $y=c+e$ is a transmitted codeword plus an error, then $s(y)=s(e)$: the syndrome determines the error coset. Choosing a minimum-weight coset leader and subtracting it performs minimum-distance decoding. The error itself need not be uniquely identified, but it is unique when its weight is at most $\lfloor (d-1)/2\rfloor$, since the corresponding error-correction balls are disjoint.

For the repetition code, the nonzero codeword is the all-ones word, soTheir product is $X^N+1$, and the generator polynomial degree $N-1$ gives dimension one. For the single parity-check code, membership is $a(1)=0$, equivalent to divisibility by $X+1$. ThusIts dimension is $N-1$; it is the even-weight code.

Finally, factor the binary length-seven modulus:A standard cyclic realization of the Hamming code of length seven usesIts dimension is four. The reciprocal-check construction givesIts columns are exactly the seven distinct nonzero vectors of ${\mathbb{F}}_2^3$, so no word of weight one or two is in its kernel. The generator itself has weight three, so the minimum Hamming distance is exactly three; this is the $[7,4,3]$ Hamming code. Reversing the cyclic coordinate order gives the equally valid reciprocal choiceThe polynomial answer therefore depends on the cyclic coordinate convention, while the resulting codes are equivalent.