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\colon R\to \mathbb {N}$

(nazywana normą), że

• $N(0)=0,$
• dla dowolnych $a,b\in R,$ gdzie $b\neq 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)\leq 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\neq 0$ można zdefiniować $N(a)$ wzorem

$N(a)=\min _{x\in R\setminus \{0\}}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\neq 0$ w przypadku, gdy $I\neq \{0\}.$ Bez straty ogólności, można przyjąć, że $v(b)$ jest minimalne, tzn. $v(b)\leq v(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ż $v(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[{\tfrac {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{cases}a=bq_{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{cases}},$

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 $v$ dana wzorem $v(p^{k}\ell /n)=k$ dla $p^{k}\ell /n\neq 0$ jest normą, tzn. $T_{p}$ jest pierścieniem Euklidesa.