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.

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.

For the polynomial ring, use the Euclidean function $\delta (f)=\mathrm{deg}f$ on nonzero polynomials. If $a,b\in F[X]$ and $b\ne 0$, subtract the multiple of $b$ that cancels the leading term of $a$. The leading coefficient of $b$ is invertible in the field, and every subtraction strictly lowers the degree of the remainder. This process terminates with $a=qb+r$ and either $r=0$ or $\mathrm{deg}r<\mathrm{deg}b$. Thus $\boxed{F[X]\text{ is a Euclidean domain}}$.

For the Gauss lemma for polynomials, call an integer polynomial primitive when its coefficient gcd is one. If two primitive polynomials had a nonprimitive product, a prime $p$ would divide every product coefficient. Reducing modulo $p$ would give a zero product of two nonzero polynomials in the integral domain ${\mathbb{F}}_p[X]$, a contradiction. Therefore the product of primitive integer polynomials is primitive.

To transfer a rational factorization, write each nonzero rational factor as a rational scalar times a primitive integer polynomial by clearing denominators and removing the coefficient gcd. Thus $f=qAB$ with primitive $A,B\in \mathbb{Z}[X]$ and $q\in \mathbb{Q}$. Their product is primitive by the lemma. If $q=m/n$ in lowest terms, integrality of every coefficient of $f$ forces $n$ to divide every coefficient of $AB$, so $n=1$. Hence $q\in \mathbb{Z}$; absorbing $q$ into either factor produces the required integer factorization with the same positive factor degrees. In particular irreducibility of a primitive polynomial over $\mathbb{Z}$ and over $\mathbb{Q}$ is equivalent.

Finally, let $a/b$ in lowest terms, $b>0$, be a rational root of a monic degree-$d$ integer polynomial. Multiplying the equation by $b^d$ shows $b\mid a^d$. Coprimality forces $b=1$. Thus $\boxed{\text{every rational root of a monic integer polynomial is an integer}}$.

For the polynomial ring, use the Euclidean function $\delta (f)=\mathrm{deg}f$ on nonzero polynomials. If $a,b\in F[X]$ and $b\ne 0$, subtract the multiple of $b$ that cancels the leading term of $a$. The leading coefficient of $b$ is invertible in the field, and every subtraction strictly lowers the degree of the remainder. This process terminates with $a=qb+r$ and either $r=0$ or $\mathrm{deg}r<\mathrm{deg}b$. Thus $\boxed{F[X]\text{ is a Euclidean domain}}$.

For the Gauss lemma for polynomials, call an integer polynomial primitive when its coefficient gcd is one. If two primitive polynomials had a nonprimitive product, a prime $p$ would divide every product coefficient. Reducing modulo $p$ would give a zero product of two nonzero polynomials in the integral domain ${\mathbb{F}}_p[X]$, a contradiction. Therefore the product of primitive integer polynomials is primitive.

To transfer a rational factorization, write each nonzero rational factor as a rational scalar times a primitive integer polynomial by clearing denominators and removing the coefficient gcd. Thus $f=qAB$ with primitive $A,B\in \mathbb{Z}[X]$ and $q\in \mathbb{Q}$. Their product is primitive by the lemma. If $q=m/n$ in lowest terms, integrality of every coefficient of $f$ forces $n$ to divide every coefficient of $AB$, so $n=1$. Hence $q\in \mathbb{Z}$; absorbing $q$ into either factor produces the required integer factorization with the same positive factor degrees. In particular irreducibility of a primitive polynomial over $\mathbb{Z}$ and over $\mathbb{Q}$ is equivalent.

Finally, let $a/b$ in lowest terms, $b>0$, be a rational root of a monic degree-$d$ integer polynomial. Multiplying the equation by $b^d$ shows $b\mid a^d$. Coprimality forces $b=1$. Thus $\boxed{\text{every rational root of a monic integer polynomial is an integer}}$.

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.

Letbe a primitive polynomial. The Eisenstein criterion states that if a prime number $p$ satisfiesthen $F$ is an irreducible polynomial in $\mathbb{Z}[X]$, equivalently in $\mathbb{Q}[X]$ by Gauss lemma for polynomials.

To prove it, suppose that $F=GH$ with $G,H\in \mathbb{Z}[X]$ of positive degree. Primitivity and Gauss's lemma let us take such an integral factorisation if a factorisation over $\mathbb{Q}$ exists. Reducing modulo $p$ givesBecause $p$ does not divide the leading coefficient of $F$, neither factor loses degree on reduction. The polynomial ring ${\mathbb{F}}_p[X]$ is a unique factorization domain, so both reductions are monomials of positive degree. In particular, $p$ divides both constant terms $G(0)$ and $H(0)$. It follows that $p^2$ dividesa contradiction. This proves the criterion.

For a prime $p$, translate the geometric sum by one:Its leading coefficient is one, every other coefficient is divisible by $p$, and its constant coefficient is $p$, which is not divisible by $p^2$. It is therefore Eisenstein at $p$. Translation $X\mapsto X+1$ is an automorphism of $\mathbb{Z}[X]$, soThis is the geometric-sum irreducibility criterion.

The evaluation homomorphismhas image $\mathbb{Z}[\zeta ]$ and contains $(f)$ in its kernel. Since $f$ is monic, division by $f$ in $\mathbb{Z}[X]$ writes every $G$ as $G=Qf+R$ with $\mathrm{deg}R<\mathrm{deg}f$. If $G(\zeta )=0$, then $R(\zeta )=0$; the irreducibility of $f$ says that $f$ is the minimal polynomial of $\zeta$, so $R=0$. Thus $\ker ({\mathrm{ev}}_{\zeta })=(f)$, and the first isomorphism theorem for rings gives

Now take $p=3$. Then ${\zeta }^2+\zeta +1=0$, and the Eisenstein integers areComplex conjugation sends $\zeta$ to ${\zeta }^2$, so the field norm isGiven $z=x+y\zeta \in \mathbb{C}$, choose integers $m,n$ with $|x-m|,|y-n|\le \frac{1}{2}$. For $q=m+n\zeta$,For $\alpha ,\beta \in \mathbb{Z}[\zeta ]$ with $\beta \ne 0$, apply this to $z=\alpha /\beta$ and put $r=\alpha -q\beta$. ThenHence the norm is a Euclidean function, proving that $\mathbb{Z}[\zeta ]$ is a Euclidean domain. This is the Euclidean norm on the Eisenstein integers.

Finally suppose $A\in {\mathrm{GL}}_n(\mathbb{Z})$ satisfies $A^2+A+I=0$. Make the free abelian group $M={\mathbb{Z}}^n$ into a $\mathbb{Z}[\zeta ]$-module by definingThis is well-defined precisely because $A$ obeys the same polynomial relation as $\zeta$. The module is finitely generated. It is also torsion-free module: if $0\ne \alpha \in \mathbb{Z}[\zeta ]$ and $\alpha v=0$, multiplication by the conjugate of $\alpha$ gives $N(\alpha )v=0$, and the additive group ${\mathbb{Z}}^n$ has no nonzero integer torsion.

A Euclidean domain is a principal ideal domain, and the structure theorem for finitely generated modules over a principal ideal domain says that a finitely generated torsion-free module over one is free. Thusfor some $m$. Since $\mathbb{Z}[\zeta ]$ has free module basis $1,\zeta$ over $\mathbb{Z}$, comparison of abelian ranks gives $n=2m$. There can consequently be no such matrix when $n$ is odd.

If $n=2m$, choose a $\mathbb{Z}[\zeta ]$-basis $v_1,\dots ,v_m$. Thenis a $\mathbb{Z}$-basis, and $A^2{v}_i=-v_i-A{v}_i$. In this basis the matrix of $A$ is a direct sum of $m$ copies ofEvery admissible matrix is therefore conjugate in ${\mathrm{GL}}_n(\mathbb{Z})$ to $C^{\oplus m}$. Hence there is exactly one conjugacy class for even $n$, and none for odd $n$. This is the classification of integral matrices satisfying the third cyclotomic polynomial.

A Euclidean domain is an integral domain $R$ with a Euclidean function $\nu :R\setminus \{0\}\to {\mathbb{Z}}_{\ge 0}$ such that, for $a,b\in R$ with $b\ne 0$, there exist $q,r\in R$ satisfyingThe polynomial ring $\mathbb{Q}[x]$ has this property with $\nu (f)=\mathrm{deg}f$. To perform polynomial division, subtract an appropriate multiple of the divisor to cancel the leading term of the current remainder. Its polynomial degree decreases strictly at each step, so the process terminates below the divisor's degree. The required division of leading coefficients is possible in the field $\mathbb{Q}$. Thus a polynomial ring over a field is Euclidean, with the same argument applying to every field.

Now let $I$ be a nonzero ideal of a Euclidean domain, and choose $b\in I\setminus \{0\}$ with the least possible value of $\nu (b)$. For every $a\in I$, divide $a=qb+r$. The remainder belongs to $I$, since $r=a-qb$. If it were nonzero, its smaller Euclidean value would contradict the choice of $b$. Thus $r=0$ and every $a\in I$ lies in $(b)$. Conversely $(b)\subseteq I$ because $I$ is an ideal. Hence $I=(b)$. The zero ideal is already $(0)$, proving every Euclidean domain is a principal ideal domain.

The Gaussian integers form an integral domain, since they are a subring of the complex numbers. Use the Gaussian integer normwhich is a positive integer for nonzero $a+bi$ and satisfies $N(\alpha \beta )=N(\alpha )N(\beta )$.

For $\alpha ,\beta \in \mathbb{Z}[i]$ with $\beta \ne 0$, write $\alpha /\beta =x+iy$. Choose integers $m,n$ with $|x-m|\le 1/2$ and $|y-n|\le 1/2$, put $q=m+in$, and set $r=\alpha -\beta q$. ThenThus division with remainder has either $r=0$ or a strictly smaller Gaussian integer norm. This proves that $N$ is a euclidean function and

For a field $F$, polynomial division makes the one-variable polynomial ring $F[X]$ a Euclidean domain with Euclidean function equal to the polynomial degree. For a divisor $g\ne 0$, subtract a suitable scalar multiple of $X^{\mathrm{deg}f-\mathrm{deg}g}g$ to cancel the leading coefficient of the current remainder. Its degree strictly decreases. Iteration terminates at $f=qg+r$, where $r=0$ or $\mathrm{deg}r<\mathrm{deg}g$. Division by the leading coefficient is valid because it is nonzero in a field.