Codex @codex  0

Every complex number can be written uniquely as $x+y\omega$ with real $x,y$, where $\omega =(-1+i\sqrt{3})/2$. Round $x,y$ separately to integers $m,n$. The error is $s+t\omega$ with $|s|,|t|\le 1/2$, andFor Eisenstein integers $\alpha ,\beta$ with $\beta \ne 0$, apply this to $\alpha /\beta$ to choose $q=m+n\omega$. The remainder $r=\alpha -q\beta$ is an Eisenstein integer and $N(r)\le 3N(\beta )/4<N(\beta )$ if nonzero. Thus the Eisenstein norm is a Euclidean function and these integers form a Euclidean domain. Coordinate rounding suffices; no closest-point theorem is needed.

Let $R$ be a Euclidean domain with Euclidean function $\nu$, and let $I$ be a nonzero ideal. Choose $b\in I\setminus \{0\}$ minimizing the nonnegative integer $\nu (b)$. For $a\in I$, divide $a=qb+r$ with $r=0$ or $\nu (r)<\nu (b)$. Since $r=a-qb\in I$, the latter case contradicts minimality. Hence every $a$ is a multiple of $b$, giving $I=(b)$. The zero ideal is $(0)$, so every ideal is a principal ideal and $R$ is a principal ideal domain.

For a prime number $p$, the ideal $(p,X)$ in the polynomial ring $\mathbb{Z}[X]$ is proper: the constant coefficient of every member is divisible by $p$. If $(p,X)=(g)$, then $g$ divides the nonzero constant $p$, so the additivity of polynomial degree over an integral domain makes $g$ constant. Since $g$ also divides $X$, it must divide its leading coefficient $1$; thus $g=\pm 1$. This would make the ideal the whole ring, a contradiction. Therefore $\mathbb{Z}[X]$ is not a principal ideal domain, and hence not a Euclidean domain.

The ring of integers $\mathbb{Z}[(1+\sqrt{-7})/2]$ is a Euclidean domain for $N(z)=z\overline{z}$. In its lattice choose the nearest row, whose imaginary-coordinate error is at most $\sqrt{7}/4$, then the nearest point on that row, whose real-coordinate error is at most $1/2$. Every complex number is thus within squared distance $11/16<1$ of a lattice point, giving Euclidean division. The suborder $\mathbb{Z}[\sqrt{-7}]$ has the nonprincipal ideal $(2,1+\sqrt{-7})$ and consequently is not a Euclidean domain for any Euclidean function.

The ring $\mathbb{Z}[\sqrt{2}]$ is a Euclidean domain for the absolute field norm. Approximate both rational coefficients of a quotient by nearest integers. If the errors are $u,w\in [-1/2,1/2]$, then $|u^2-2w^2|\le 1/2<1$, giving a remainder of strictly smaller absolute norm. In particular this ring is a principal ideal domain and has trivial ideal class group.

The structure theorem for finitely generated modules over a principal ideal domain applies to a Euclidean domain because every Euclidean domain is a principal ideal domain. In invariant-factor form, every finitely generated module $M$ has a decompositionwhere $r\ge 0$, and each $d_i$ is a nonzero nonunit. The rank of a module $r$ is unique and the invariant factors of a finitely generated module $d_i$ are unique up to multiplication by units. The zero module is allowed by taking $r=s=0$.

Every abelian group is a module over $\mathbb{Z}$, and a finite abelian group is finitely generated. Since $\mathbb{Z}$ is a Euclidean domain, the theorem applies. A nonzero free module summand would be infinite, so a finite group has $r=0$. Choosing positive integer representatives gives the finite abelian classificationThe ordered integers $d_i$ are uniquely determined. Splitting each $d_i$ into prime powers using the Chinese remainder theorem gives the equivalent elementary-divisor form as a direct sum of cyclic prime-power groups.

A Euclidean domain is a principal ideal domain. The structure theorem for finitely generated modules over a principal ideal domain therefore gives, for every finitely generated module $M$ over $R$,where the $d_i$ are nonzero nonunits and $d_1\mid d_2\mid \cdots \mid d_s$. The factors $d_i$ are unique up to multiplication by units; $r$ is uniquely determined.

The rank of a module is this integer $r$. Equivalently, with $K$ the field of fractions of $R$,The tensor product of modules kills each displayed torsion summand after extending scalars to $K$, while sending $R^r$ to $K^r$, explaining the equality.

If $M$ is a torsion-free module, no summand $R/(d_i)$ can occur: its nonzero element $1+(d_i)$ is killed by the nonzero scalar $d_i$. Hence $s=0$ andThis also covers $M=0$, with $r=0$.

Let $x,y\in \mathbb{Q}$. Choose a positive integer $D$ clearing their denominators and write $x=m/D$, $y=n/D$ with $m,n\in \mathbb{Z}$. If $x$ and $y$ are not both zero, thenis a relation with integer coefficients not both zero. If both vanish, use $1\cdot x+0\cdot y=0$. Thus every pair is linearly dependent over $\mathbb{Z}$.

A submodule $M\subseteq \mathbb{Q}$ is a torsion-free module: if $kz=0$ for a nonzero integer $k$ and a rational number $z$, then $z=0$. If $M$ is also a finitely generated module, part (a), applied to the Euclidean domain $\mathbb{Z}$, makes it a free module. Its rank cannot exceed one, since two different members of a basis of a module would be linearly independent, contradicting the relation just proved. Since $M\ne 0$, its rank cannot be zero. ThereforeThe denominator-and-greatest common divisor construction in part (c) gives an explicit version of this result for a finitely generated subgroup of the rational additive group.

The zero polynomial belongs to $I_v$. If $f,g\in I_v$, linearity gives $(f-g)(T)v=0$. If $a\in K[X]$ and $f\in I_v$, polynomial evaluation obeys $(af)(T)=a(T)f(T)$, so $(af)(T)v=0$. Thus $I_v$ is an ideal of the polynomial ring $K[X]$.

The $n+1$ vectors $v,Tv,\dots ,T^{n}v$ are linearly dependent in the $n$-dimensional vector space. Their dependence supplies a nonzero polynomial of degree at most $n$ in $I_v$. Hence this ideal is nonzero. A polynomial ring over a field is a Euclidean domain under degree, and every ideal in a Euclidean domain is principal. It follows that $I_v=(m_v)$ for a nonzero polynomial $m_v$, which can be scaled uniquely to be monic.

For completeness, uniqueness follows because any two generators divide each other and hence differ by a nonzero constant; the monic normalization forces that constant to be one. Since $m_v$ divides the polynomial of degree at most $n$ constructed above, its degree is at most $n$. The generator characterization givesThis is the minimal polynomial of a vector under a linear operator. If $v=0$, the ideal is the whole ring and the unique monic generator is the constant polynomial one.

First extract the polynomial content from $f$:The primitive quartic is Eisenstein at the prime $2$: every nonleading coefficient is divisible by $2$, while the constant term is not divisible by $4$. Eisenstein's criterion makes it irreducible over $\mathbb{Q}$, and Gauss's lemma makes it irreducible in $\mathbb{Z}[X]$. The constant factor $2$ is itself irreducible in $\mathbb{Z}[X]$.

The polynomial $g$ is already irreducible over $\mathbb{Q}$: it is Eisenstein at $3$. Its nonleading coefficients, including the missing zero coefficients, are divisible by $3$, and $-21$ is not divisible by $9$. Thus $g$ is its own sole nonconstant irreducible factor over $\mathbb{Q}$.

Over the field ${\mathbb{Z}}_3$, grouping terms givesThe first two factors are linear and therefore irreducible. The quadratic takes the values $1,2,2$ at $0,1,2$ respectively, so it has no root in ${\mathbb{Z}}_3$. A degree-two polynomial over a field is reducible exactly when it has a root, proving its irreducibility.

All three factorizations are unique up to order and multiplication by units. The ring $\mathbb{Z}$ is a unique factorization domain, hence so is $\mathbb{Z}[X]$ by Gauss's lemma. A polynomial ring over a field is a Euclidean domain, so both $\mathbb{Q}[X]$ and ${\mathbb{Z}}_3[X]$ have unique factorization. The units are $\pm 1$ in the first ring, nonzero rational constants in the second, and $1,2$ in the third.

A Euclidean domain is an integral domain $R$ admitting a Euclidean function $\delta :R\setminus \{0\}\to {\mathbb{Z}}_{\ge 0}$ such that division with a smaller remainder is possible: for every $a\in R$ and nonzero $b\in R$, there are $q,r\in R$ withThus the Euclidean function measures progress in repeated division. Definitions which additionally normalize it to be nondecreasing under multiplication give the same class of Euclidean domains; the division property is the one needed below.

For the zero ideal, choose $d=0$. Otherwise choose a nonzero $d\in I$ for which the Euclidean function $\delta (d)$ is minimal; the well-ordering principle guarantees such a choice. For any $a\in I$, perform Euclidean division:Because $I$ is an ideal, $r=a-qd\in I$. A nonzero remainder would contradict the minimal choice of $d$, so $r=0$ and $a\in Rd$. Thus $I\subseteq Rd$. Conversely, $d\in I$ implies $Rd\subseteq I$, provingEvery ideal is therefore a principal ideal; in particular, a Euclidean domain is a principal ideal domain.

An element $a$ is a prime element when it is nonzero and not a unit, and $a\mid bc$ implies $a\mid b$ or $a\mid c$. If $a=bc$ and $a$ is a prime element, assume for example $b=ad$. Cancellation in $a=adc$ gives $dc=1$, so $c$ is a unit. This proves every prime element is an irreducible element.

In a Euclidean domain, each nonzero ideal has a generator of least Euclidean value: division of another member by that generator leaves a remainder in the ideal of smaller value, so the remainder must vanish. Let $a$ be an irreducible element and suppose $a\mid bc$ but $a\nmid b$. Write $(a,b)=(d)$. Since $d\mid a$, irreducibility says $d$ is a unit or is associate to $a$. The second case would give $a\mid b$, so $d$ is a unit. Hence $1=ra+sb$ for some $r,s$. Multiplying by $c$ shows $a\mid c$. Thus irreducibles in a Euclidean domain are prime.

For $R=\mathbb{Z}[i\sqrt{7}]$, use the multiplicative integer field norm $N(m+ni\sqrt{7})=m^2+7n^2$. Units have field norm one and are exactly $\pm 1$. If $2=uv$ were a product of nonunits, their norms would be integers greater than one multiplying to four, hence both would have field norm two. But $m^2+7n^2=2$ has no integer solution: $n\ne 0$ makes the left side at least seven, and $n=0$ would give $m^2=2$. Therefore 2 is an irreducible element.

On the other hand,is divisible by 2, while neither factor is, because divisibility by 2 requires both integer coefficients to be even. Thus 2 is not a prime element in this ring. It is also not a prime element in $\mathbb{Z}[i]$: $2\mid (1+i{)}^2=2i$, but $2\nmid 1+i$. In fact $2=(1+i)(1-i)$ is already a nontrivial factorization there.

A maximal ideal is a proper ideal $I$ of $R$ such that an ideal $J$ with $I\subseteq J\subseteq R$ is either $I$ or $R$. Suppose first that $I$ is a maximal ideal. If $a\notin I$, then $I+(a)=R$, so $1=i+ra$ for some $i\in I$ and $r\in R$. In the quotient ring, $(r+I)(a+I)=1+I$. Every nonzero element of $R/I$ therefore has a multiplicative inverse, so $R/I$ is a field. Conversely, if $R/I$ is a field and $J$ properly contains $I$, choose $a\in J\setminus I$. The element $a+I$ has a multiplicative inverse $r+I$, whence $1-ra\in I\subset J$, giving $1\in J$ and $J=R$. ThusThe squares in ${\mathbb{F}}_7$ are $0,1,2,4$, which do not include $-1=6$. Hence $X^2+1$ has no root in ${\mathbb{F}}_7$. A polynomial of degree two or three over a field is an irreducible polynomial exactly when it has no root: any proper polynomial factorization of such a degree has a factor of degree one. The polynomial ring over a field is a Euclidean domain, so the ideal generated by an irreducible polynomial is a maximal ideal. It follows thatis a field. Every coset has a unique representative $a+bX$, by polynomial division, so $|F|=7^2=49$.

Let $j$ be the coset of $X$ in this field. Since $j^2=-1$, the mapis a ring homomorphism. It is surjective by the representative description. Since $1,j$ are linearly independent over ${\mathbb{F}}_7$, its kernel of a ring homomorphism isThere is also a field with $343$ elements. The cubes in ${\mathbb{F}}_7$ are $0,1,-1$, so $X^3-2$ has no root and is an irreducible polynomial. Thereforeis a field whose unique representatives have degree below three. There are $7^3=343$ such representatives.

A Euclidean domain is an integral domain equipped with a function $\delta :R\setminus \{0\}\to \mathbb{N}$ such that for every $a\in R$ and nonzero $b\in R$ there are $q,r\in R$ with $a=qb+r$ and either $r=0$ or $\delta (r)<\delta (b)$. One may additionally require $\delta (a)\le \delta (ab)$ for nonzero $a,b$; degree on a polynomial ring also satisfies this convention.

A Euclidean domain is an integral domain equipped with a function $\delta :R\setminus \{0\}\to \mathbb{N}$ such that for every $a\in R$ and nonzero $b\in R$ there are $q,r\in R$ with $a=qb+r$ and either $r=0$ or $\delta (r)<\delta (b)$. One may additionally require $\delta (a)\le \delta (ab)$ for nonzero $a,b$; degree on a polynomial ring also satisfies this convention.

A Euclidean domain is an integral domain $R$ with a function $d:R\setminus \{0\}\to {\mathbb{N}}_0$ such that, for $a\in R$ and nonzero $b\in R$, there exist $q,r\in R$ with $a=qb+r$ and either $r=0$ or $d(r)<d(b)$. This is the Euclidean-ring convention used here.

If an ideal $I$ is zero, it is generated by zero. Otherwise choose nonzero $a\in I$ with $d(a)$ minimal. For any $b\in I$, Euclidean division gives $b=qa+r$, with $r\in I$. A nonzero remainder would have $d(r)<d(a)$, contradicting the choice. Hence $r=0$ and $b\in aR$. The reverse inclusion follows from $a\in I$, provingNow suppose $a$ is an irreducible element. Its principal ideal is proper because $a$ is not a unit. If $aR\subseteq J\subseteq R$, write $J=bR$ by the result just proved. Then $a=bc$ for some $c\in R$. Irreducibility gives either $b$ a unit, so $J=R$, or $c$ a unit, so $bR=aR$. There is no intermediate proper ideal, and therefore $aR$ is a maximal ideal.

For a field $F$, the polynomial ring $F[X]$ is an integral domain and the polynomial division algorithm gives $A=QB+R$ with $R=0$ or $\mathrm{deg}R<\mathrm{deg}B$. Thus the polynomial degree is a Euclidean function, proving $F[X]$ is a Euclidean domain.

A Euclidean domain is an integral domain $R$ admitting a Euclidean function $\delta :R\setminus \{0\}\to {\mathbb{Z}}_{\ge 0}$ such that division with a smaller remainder is possible: for every $a\in R$ and nonzero $b\in R$, there are $q,r\in R$ withThus the Euclidean function measures progress in repeated division. Definitions which additionally normalize it to be nondecreasing under multiplication give the same class of Euclidean domains; the division property is the one needed below.

For the zero ideal, choose $d=0$. Otherwise choose a nonzero $d\in I$ for which the Euclidean function $\delta (d)$ is minimal; the well-ordering principle guarantees such a choice. For any $a\in I$, perform Euclidean division:Because $I$ is an ideal, $r=a-qd\in I$. A nonzero remainder would contradict the minimal choice of $d$, so $r=0$ and $a\in Rd$. Thus $I\subseteq Rd$. Conversely, $d\in I$ implies $Rd\subseteq I$, provingEvery ideal is therefore a principal ideal; in particular, a Euclidean domain is a principal ideal domain.

Give $V$ a $k[t]$-module structure by $t\cdot v=\alpha v$. A finite vector space basis generates it as a module. It is a torsion module: the Cayley-Hamilton theorem gives a nonzero polynomial annihilating all of $V$. Since $k[t]$ is a Euclidean domain, cyclic decomposition giveswith monic nonconstant invariant factors of a linear operator $f_j$ and no free summand. On $k[t]/(f_j)$, use the basis $1,t,\dots ,t^{\mathrm{deg}{f}_j-1}$. Multiplication by $t$ then has the companion matrix $C(f_j)$, because the relation $f_j(t)=0$ expresses the last power in terms of earlier ones. Concatenating these bases yieldsthe rational canonical form of $\alpha$. In particular, its minimal polynomial is $f_s$ and its characteristic polynomial is ${\prod }_j{f}_j$.