# 小科普之Principal Ideal Domain is not necessarily Euclidean Domain

It's a well known fact that Euclidean domains are principal ideal domain by taking the element in a certain ideal with smallest \varphi value. Yet the converse is false, and one counterexample just lies among our familiar algebraic integer rings, \mathbb Z \left({1+\sqrt{19}i\over2}\right). Actually with proper introduction on the idea of norm like the setting of which on Hungerford's book, even beginner can prove this fact with just a little effort.

Firstly we introduce the important notion from algebraic number theory: norm. A norm is a map N_{K/L}:K\rightarrow \mathbb C where K/L is an algebraic extension such that N_{K/L}(\alpha)=\prod \sigma_i(\alpha), where \sigma_i(\alpha) are the roots of the minimal polynomial in K[x] of \alpha. Here we absolutely do not need such detailed definition and proof of its consequences but some examples, like N_{\mathbb Q(i)/\mathbb Q}(a+bi)=a^2+b^2, N_{\mathbb Q(\sqrt{10})/\mathbb Q}(a+b\sqrt{10})=a^2-10b^2, where in both cases restricting N to K\cap\mathcal O, the subring of algebraic integers of K, codomain of N is \mathbb Z, N(\alpha)=0 iff \alpha=0, N(\alpha)=\pm1 iff \alpha is a unit, and N(\alpha)N(\beta)=N(\alpha\beta).

Denoting z={1+\sqrt{19}i\over2}, whose minimal polynomial is x^2-x+5, we define norm on R=\mathbb Z \left({1+\sqrt{19}i\over2}\right) by N(a+bz)=(a+bz)(a+b\bar z)=a^2+ab+5b^2 where a,b\in\mathbb Z. It's easy to demonstrate the results above and image of N lies in \mathbb N.

R is a PID: it's obvious that R is an integral domain. For any ideal I, take nonzero x with minimal norm. If N(x)=1, x is unit, so clearly R=(x)\subset I\subset R, namely I=(x). Otherwise if \exists y\in I-(x), we seek p,q\in R s.t. 0<N(py-qx)<N(x), obtaining contradiction. Considering equivalent condition 0<N(py\bar x-qx\bar x)<N(x\bar x), wlog assume x\in \mathbb N with x\ge 2. Denote y=a+bz, p=p_1+p_2z, q=q_1+q_2z, we want 0<A^2+AB+5B^2<1 where A=p_1 a/x-5p_2 b/x-q_1, B=p_1b/x+p_2a/x+p_2b/x-q_2. WLOG assume 0\le a/x,b/x<1 by substracting integer part using q_1,q_2. Rewriting a/x=n_1/m_1, b/x=n_2/m_2 where either n_i=0 or (n_i,m_i)=1 and m_i>0 for i=1,2. When b/x=0, then a/x\ne0. Let p_2=0,p_1=1, then q_1=q_2=0, then 0<(a/x)^2=A^2+AB+5B^2<1. When b/x=1/2, if a/x=0, let p_2=1,p_1=-1, and q_1=-3,q_2=0, then A=1/2,B=0, the result is desired. Else if b/x=1/2,m_1\ge 3, find p_1'n_1-q_1'm_1=1, which exists as (n_1,m_1)=1, and let p_1=2p_1',q_1=2q_1',p_2=0,q_2=p_1', then 0<A=(p_1n_1-q_1m_1)/m_1\le2/3,B=0, also fulfilling goal. Finally if m_2\ge 3, let p_2=0, and find p_1n_2-q_2m_2=1, then we can surely choose q_1 s.t. |p_1a/x-q_1|\le1/2 by rounding p_1a/x. Then 0<A^2+AB+5B^2 as B\ne 0, and A^2+AB+5B^2\le A^2+|AB|+5B^2\le(1/2)^2+(1/2)(1/3)+5(1/3)^2=35/36<1!

Of course the case distinction above can be greatly simplified if you know class groups and Minkowski approximation, which is a pretty elementary combinatoric geometry trick. For more one can read Ben Green's notes on algebraic number theory for Oxford. Here we just provided one proof suitable for those with less background.

R is not Euclidean: if there is \varphi:R-\lbrace0\rbrace\rightarrow\mathbb N s.t. \varphi(x)\le\varphi(xy), \exists q,r with y=qx+r and \varphi(r)<\varphi(x) or r=0 for all x,y\in R-\lbrace0\rbrace, take a nonzero nonunit x with minimal \varphi value, and we can assume wlog x is irreducible as R is PID hence UFD and taking any irreducible factor of nonunit x would work. Then for all y we have y=qx+r where r=0,-1,1 as only r with \varphi(r)<\varphi(x) are units. Assume x=x_1+x_2z, when q=q_1+q_2z, qx=x_1q_1-5x_2q_2+(x_2q_1+x_1q_2+x_2q_2)z. If x_2=0, x_2q_1+x_1q_2+x_2q_2=x_1q_2 and x_1\ne 0,1,-1, so as long as y=m+nz with x_1\nmid n q_2 has no solution. Else if x_1+x_2=0, similary x_2=\pm1, wlog let it be 1, then x_1=-1, and if y=m+nz we have q_1=n. When m-n\not\equiv 0,1,-1(\text{mod}\ 5) there's no solution for q_2. Otherwise consider y=m+x_2z, we have q_1,q_2 s.t. m=x_1q_1-5x_2q_2+r and x_2=(x_1+x_2)q_2+x_2q_1. As x_1+x_2,x_2\ne0 and x irreducible, (x_1+x_2,x_2)=1, so the solution to x_2=(x_1+x_2)q_2+x_2q_1 can only be q_1=1+k(x_1+x_2),q_2=-kx_2, then m=x_1+k(x_1^2+x_1x_2+5x_2^2)=x_1+kN(x). As x is nonzero nonunit, it's clear that N(x)\ge 4. Now if we choose m s.t. m-x_1\not\equiv0,1,-1(\text{mod}\ N(x)) there's no solution for k.

THE END