Dziedzina Euklidesa

Dziedzina Euklidesa – w teorii pierścieni najbardziej ogólny typ pierścieni, w którym możliwe jest wyznaczenie największego wspólnego dzielnika za pomocą algorytmu Euklidesa. Dziedziny Euklidesa są dziedzinami całkowitości. Obiekty te nazywa się także pierścieniami Euklidesa.

Definicja

Dziedzinę całkowitości R nazywa się dziedziną Euklidesa, jeżeli istnieje taka funkcja $N\colon R \to \mathbb N$ (nazywana "normą"), że

• $N(0)=0\,$,
• dla dowolnych $a, b \in R,$ przy czym $b \ne 0$, istnieją takie $q, r \in R$ dla których

$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) \leqslant N(ab)$ dla $a, b \in R$.

Można jednak dowieść, że powyższy warunek nie jest istotny: 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 (Rogers 1971)

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

Własności

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

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 pewnego $k \in \mathbb N$ jest 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 oraz b.

Przykłady

Pierścieniami Euklidesa są na przykład:

• pierścień liczb całkowitych z N(x) = | x | ,
• pierścień liczb całkowitych Eisensteina,
• pierścień $\mathbb Z[i]$ wraz z N(z) = a² + b² dla z = a + bi,
• pierścień wielomianów nad dowolnym ciałem z N określonym jako stopień wielomianu.