Dziedzina Euklidesa - Polski Serwis Naukowy

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.

Algorytm Euklidesa – algorytm znajdowania największego wspólnego dzielnika (NWD) dwóch liczb naturalnych. Nie wymaga rozkładania liczb na czynniki pierwsze. Algorytm wymyślił Eudoksos z Knidos (IV wiek p.n.e.), a Euklides jedynie zawarł go w swoim dziele Elementy.

Ciało – struktura formalizująca własności algebraiczne liczb wymiernych, czy liczb rzeczywistych. W trakcie badań nad tymi obiektami rozwinął się aparat matematyczny (tzw. teoria Galois) umożliwiający rozwiązanie takich problemów jak rozwiązalność równań wielomianowych (jednej zmiennej) przez tzw. pierwiastniki (działania obowiązujące w ciałach i wyciąganie pierwiastków), czy wykonalność pewnych konstrukcji klasycznych (konstrukcji geometrycznych, w których dozwolone jest korzystanie z wyidealizowanych cyrkla i linijki). Działem matematyki zajmującym się opisem tych struktur jest teoria ciał.

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)

Największy wspólny dzielnik – dla danych dwóch (lub więcej) liczb całkowitych największa liczba naturalna dzieląca każdą z nich. Pojęcie to ma wiele uogólnień, które przedstawiono w dalszej części artykułu.

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