Dziedzina Euklidesa

Dziedzina Euklidesa (albo pierścień Euklidesa, pierścień euklidesowy) – najbardziej ogólny typ pierścieni, w którym możliwe jest wyznaczenie największego wspólnego dzielnika za pomocą algorytmu Euklidesa.

Definicja

Dziedzinę całkowitości $R$ nazywa się dziedziną Euklidesa (albo pierścieniem Euklidesa, pierścieniem euklidesowym), jeżeli istnieje taka funkcja

$N:R\to \mathbb{N}$

(nazywana normą), że

• $N(0)=0,$
• dla dowolnych $a,b\in R,$ gdzie $b\ne 0,$ istnieją takie $q,r\in R,$ że

$a=bq+r$

oraz zachodzi jeden z warunków: $r=0$ lub $N(r)<N(b).$

Czasami dodatkowo przyjmuje się również, że:

• $N(a)\le N(ab)$ dla $a,b\in R,$

jednak nie jest to konieczne: każda dziedzina całkowitości $R,$ która może być wyposażona w funkcję $M$ spełniającą pierwsze dwa warunki, może być również wyposażona w funkcję $N$ spełniającą również trzeci warunek. Istotnie, dla $a\ne 0$ można zdefiniować $N(a)$ wzorem

$N(a)=\underset{x\in R\setminus \{0\}}{\min }M(xa).$

Własności

Każdy pierścień Euklidesa jest pierścieniem ideałów głównych.

Dowód. Każdy pierścień Euklidesa jest z definicji dziedziną całkowitości. Należy wykazać, że jeżeli $I$ jest ideałem w pierścieniu Euklidesa $R,$ to $I=bR$ dla pewnego $b\in R.$ Jeżeli $I=\{0\},$ $I=0R.$ Niech $b\in I,$ $b\ne 0$ w przypadku, gdy $I\ne \{0\}.$ Bez straty ogólności, można przyjąć, że $N(b)$ jest minimalne, tzn. $N(b)\le N(a)$ dla każdego niezerowego $a\in R.$ Twierdzimy, że $I=bR.$ Ponieważ $b\in I,$ zachodzi inkluzja $bR\subseteq I,$ należy zatem wykazać inkluzję przeciwną. Niech $a\in I.$ Istnieją zatem takie $q,r\in R,$ że $a=qb+r.$ Ponieważ $N(b)$ jest minimalne, $r=0,$ czyli zachodzi równość $a=qb,$ tj. $a\in bR,$ co dowodzi inkluzji $I\subseteq bR.$

Istnieją pierścienie ideałów głównych, których nie da się wyposażyć w normę (tj. nie są pierścieniami euklidesowymi). Przykładem takiego pierścienia jest

$\mathbb{Z}\left[\frac{1+\sqrt{19}\mathrm{i}}{2}\right].$

Największy wspólny dzielnik dwóch niezerowych elementów pierścienia Euklidesa można odnaleźć przy pomocy algorytmu Euklidesa. Jeżeli $R$ jest pierścieniem Euklidesa $a,b\in R\setminus \{0\},$ to można utworzyć taki ciąg równości

$\{\begin{array}{c}a=b{q}_1+r_1\\ b=r_1{q}_2+r_2\\ r_1=r_2{q}_3+r_3\\ r_2=r_3{q}_4+r_4\\ \dots \end{array},$

aby

$N(b)>N(r_1)>N(r_2)>\dots$

Ciąg taki (jako malejący ciąg liczb całkowitych dodatnich) musi być skończony, zatem dla pewnej liczby naturalnej $k$ zachodzi równość $r_{k+1}=0.$ Dla najmniejszego takiego $k$ reszta $r_k$ jest największym wspólnym dzielnikiem elementów $a,b\in R.$ Zatem jeśli można wyznaczyć $q_1,q_2,\dots$ i $r_1,r_2,\dots ,$ to można wyznaczyć największy wspólny dzielnik $a$ i $b.$

Przykłady

Pierścieniami Euklidesa są:

• Pierścień liczb całkowitych z normą $N(x)=|x|,$
• Pierścień $\mathbb{Z}[\text{i}]$ liczb całkowitych Gaussa wraz z normą $N(z)=a^2+b^2,$ gdzie $z=a+b\text{i},$
• Pierścień $\mathbb{Z}[e^{2\pi \text{i}/3}]$ liczb całkowitych Eisensteina z normą $N(z)=a^2+b^2-ab,$ gdzie $z=a+b\cdot e^{2\pi \text{i}/3},$
• Pierścień wielomianów $F[x]$ nad dowolnym ciałem $F$ wyposażony z normę $N(f)$ = stopień wielomianu $f$ jest pierścieniem Euklidesa. Dokładniej, własność ta charakteryzuje ciała pośród pierścieni, gdyż dla dowolnego pierścienia $R$ następujące warunki są równoważne:
  • $R$ jest ciałem,
  • Pierścień wielomianów $R[x]$ jest pierścieniem Euklidesowym,
  • Pierścień wielomianów $R[x]$ jest pierścieniem ideałów głównych.

• Niech $p$ będzie liczbą pierwszą oraz niech $T_p$ oznacza rodzinę liczb wymiernych postaci $m/n,$ dla których $p$ nie dzieli $n.$ Rodzina $T_p$ jest podpierścieniem ciała liczb wymiernych. Każdy element pierścienia $T_p$ może być zapisany w postaci $p^k\ell /n,$ gdzie $p$ nie dzieli ani $\ell ,$ ani $n.$ Funkcja $N$ dana wzorem $N(p^k\ell /n)=k$ dla $p^k\ell /n\ne 0$ jest normą, tzn. $T_p$ jest pierścieniem Euklidesa.