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 ${\displaystyle R}$ nazywa się dziedziną Euklidesa (albo pierścieniem Euklidesa, pierścieniem euklidesowym), jeżeli istnieje taka funkcja

${\displaystyle N\colon R\to \mathbb {N} }$

(nazywana normą), że

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

${\displaystyle a=bq+r}$

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

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

• ${\displaystyle N(a)\leq N(ab)}$ dla ${\displaystyle a,b\in R,}$

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

${\displaystyle 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 ${\displaystyle I}$ jest ideałem w pierścieniu Euklidesa ${\displaystyle R,}$ to ${\displaystyle I=bR}$ dla pewnego ${\displaystyle b\in R.}$ Jeżeli ${\displaystyle I=\{0\},}$ ${\displaystyle I=0R.}$ Niech ${\displaystyle b\in I,}$ ${\displaystyle b\neq 0}$ w przypadku, gdy ${\displaystyle I\neq \{0\}.}$ Bez straty ogólności, można przyjąć, że ${\displaystyle v(b)}$ jest minimalne, tzn. ${\displaystyle v(b)\leq v(a)}$ dla każdego niezerowego ${\displaystyle a\in R.}$ Twierdzimy, że ${\displaystyle I=bR.}$ Ponieważ ${\displaystyle b\in I,}$ zachodzi inkluzja ${\displaystyle bR\subseteq I,}$ należy zatem wykazać inkluzję przeciwną. Niech ${\displaystyle a\in I.}$ Istnieją zatem takie ${\displaystyle q,r\in R,}$ że ${\displaystyle a=qb+r.}$ Ponieważ ${\displaystyle v(b)}$ jest minimalne, ${\displaystyle r=0,}$ czyli zachodzi równość ${\displaystyle a=qb,}$ tj. ${\displaystyle a\in bR,}$ co dowodzi inkluzji ${\displaystyle 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

${\displaystyle \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 ${\displaystyle R}$ jest pierścieniem Euklidesa ${\displaystyle a,b\in R\setminus \{0\},}$ to można utworzyć taki ciąg równości

${\displaystyle {\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

${\displaystyle 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 ${\displaystyle k}$ zachodzi równość ${\displaystyle r_{k+1}=0.}$ Dla najmniejszego takiego ${\displaystyle k}$ reszta ${\displaystyle r_{k}}$ jest największym wspólnym dzielnikiem elementów ${\displaystyle a,b\in R.}$ Zatem jeśli można wyznaczyć ${\displaystyle q_{1},q_{2},\dots }$ i ${\displaystyle r_{1},r_{2},\dots ,}$ to można wyznaczyć największy wspólny dzielnik ${\displaystyle a}$ i ${\displaystyle b.}$

Przykłady

Pierścieniami Euklidesa są:

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

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