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 [edytuj]

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 [edytuj]

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.$