# Why is $\mathbb{Z}[X]$ not a euclidean domain? What goes wrong with the degree function?

I know that $K[X]$ is a Euclidean domain but $\mathbb{Z}[X]$ is not.

I understand this, if I consider the ideal $\langle X,2 \rangle$ which is a principal ideal of $K[X]$ but not of $\mathbb{Z}[X]$. So $\mathbb{Z}[X]$ isn't a principal ideal domain and therefore not an Euclidean domain.

But I don't understand this, if I consider the definition of Euclidean domains. Basically, a Euclidean domain is a ring where I can do division with remainders. For polynomial rings, the Euclidean function should be the degree of the polynomials. What's the crucial difference between $K[X]$ and $\mathbb{Z}[X]$ with respect to this?

I already did exercises involving polynomial division in $\mathbb{Z}[X]$, so clearly I must be missing something here.

• I think the problem is there are irreducibles of degree zero in there, the primes in $\Bbb Z$ Commented May 26, 2015 at 20:54
• Try writing $x^2 + 1 = 2x * q(x) + r(x)$ with deg r < deg (2x) = 1
– jxnh
Commented May 26, 2015 at 20:55
• Although $\mathbb{Z}[x]$ is not Euclidean domain, still we are able to simulate polynomial division or gcd algorithm, because of Gauss's lemma which breaks the initial polynomial into content and primitive part, thus making division possible for the primitive part. See Modern Computer Algebra by Gathen. Commented Mar 1, 2017 at 12:24
• @PranavBisht: "Thus making division possible for the primitive part." That assertion is false. $2x+1$ and $3x+1$ are both primitive. How do you divide $2x+1$ by $3x+1$ with remainder? You seem to be conflating the fact that $\mathbb{Z}[x]$ is a UFD (and thus the gcd can be defined) with the Euclidean algorithm. You can't. For example, $\gcd(x,2)=1$, but there is no way to express $1$ as $xp(x)+2q(x)$. You can do division by $p(x)$ if the leading coefficient of $p(x)$ is a unit ($1$ or $-1$), which will imply $p(x)$ is primitive; but you cannot divide by any primitive polynomial. Commented Sep 22, 2021 at 1:08
• @ArturoMagidin Yes, I see. We cannot run Euclidean algorithm on $\mathbb{Z}[x]$ but only on $\mathbb{Q}[x]$. For computing gcd in $\mathbb{Z}[x]$, we use Gauss's Lemma and Euclidean division in $\mathbb{Q}[x]$. Commented Sep 22, 2021 at 8:07

Try to divide something like $x+1$ by $2x+1$. If it were a Euclidean Domain, you should be able to write $x+1=q(x)(2x+1) + r(x)$ where $r(x)$ has to have degree 0. You can see why this is not possible to do by looking at the coefficient on the $x$ term, since $2$ is not invertible in $\mathbb{Z}$

In $$K[x]$$ the reason things go nicely is because every non-zero element in $$K$$ is invertible ($$K$$ being a field). So we can have $$a(x)=b(x)q(x)+r(x) \qquad \text{ with } \qquad 0 \leq \operatorname{deg}r(x) < \operatorname{deg}b(x).$$

But one of the problems in executing this in $$\mathbb{Z}[x]$$ is that unless the polynomial is monic you may not have the degree inequality (which is one the requirements of Euclidean Norm function). For example, if you try to carry out division with $$a(x)=x+1$$ and $$b(x)=2x$$, then you cannot have the degree of the remainder less than $$1$$. Thereby it does not fulfill the required conditions of an Euclidean Domain.

Try perform a division with remainder between $X$ and $2$ in $\mathbb Z[X]$.

Suppose you have a Euclidean domain. I claim that any element $x$ with $\deg x = 0$ should be invertible. Indeed the claim of the division algorithm gives that I can write $1 = qx + r$ with $r = 0$ or $\deg r < \deg x$. The latter is impossible if the degree is $0$, so $r = 0$ and thus $qx = 1$, giving that it is a unit.

Thus the explicit obstruction is that there are integers with degree 0 that are not invertible in the polynomial ring.

In fact, let $R$ be an integral domain and consider the ring $R[x]$ with the degree function. Then if $R[x]$ were a Euclidean domain under the degree function, every $r \neq 0 \in R$ would be invertible in $R[x]$, but since $R$ is an integral domain it is easy to see this cannot happen without $r$ being invertible in $R$. So $R$ is a field.

Take the two polynomial of $\mathbb{Z}[X]$, $P(X)=X^2+1$ and $Q(X)=2X$ and try to perform the division while keeping integer coefficients.

You can see the obstruction is coming from non invertible elements of the ring $\mathbb{Z}$

In a Euclidean domain every element $$\,a\!\ne\! 0\,$$ with $$\,\rm\color{#c00}{minimal}\,$$ Euclidean value is a unit (invertible), else $$\,a\nmid b\,$$ for some $$\,b\,$$ so $$\,b\div a\,$$ has nonzero remainder smaller than $$\,a,$$ contra minimality of $$\,a.\,$$ So if polynomial degree is a Euclidean function in $$R[x]$$ then every $$\,a\neq 0\,$$ of $$\,\rm\color{#c00}{degree\ 0}\,$$ is a unit, thus the coefficient ring $$R$$ is a field.

Remark  This is a special case of the general proof that ideals are principal in Euclidean domains (generated by any minimal element), since any element $$\neq 0\,$$ of $$\,I\,$$ of least Euclidean value divides every other element, else the remainder is a smaller element of $$I.$$ Above is special case $$\,I = (1).\,$$ In the PID $$\,k[x]$$ such minimal element generators are knowns as "minimal polynomials".

Similar ideas can be used to prove that certain quadratic number rings are not Euclidean, e.g. see the use of a "universal side divisor" in the proof of Lenstra linked in this answer. One can obtain a deeper understanding of Euclidean domains from the excellent exposition by Hendrik Lenstra in Mathematical Intelligencer $$1979/1980$$ (Euclidean Number Fields $$1,2,3$$).

$$\mathbb{Z}[X]$$ is not PID since $$\langle 2,x\rangle$$ is not principal. So if $$\mathbb{Z}[X]$$ were euclidian it would be PID.

In a PID, any irreducible element generates a maximal ideal. In $\mathbf Z[X]$, both $2$ and $X$, say are irreducible, but they're no maximal, since: $$\mathbf Z[X]/2\mathbf Z[X]\simeq(\mathbf Z/2\mathbf Z)[X]\quad\text{and}\mathbf Z[X]/X\mathbf Z[X]\simeq\mathbf Z,$$ which are not fields.