Dziedzina Euklidesa

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Dziedzina Euklidesa (albo pierścień Euklidesa, pierścień euklidesowy) – 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.

Definicja[edytuj | edytuj kod]

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, bR, gdzie b ≠ 0, istnieją takie q, rR, ż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) ≤ N(ab) dla a, bR,

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 ≠ 0 można zdefiniować N(a) wzorem

N(a) = \min_{x\in R\setminus\{0\}} M(xa).

Własności[edytuj | edytuj kod]

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 bR. Jeżeli I = {0}, I = 0R. Niech bI, b ≠ 0 w przypadku, gdy I ≠ {0}. Bez straty ogólności, można przyjąć, że v(b) jest minimalne, tzn. v(b) ≤ v(a) dla każdego niezerowego aR. Twierdzimy, że I = bR. Ponieważ, bI, zachodzi inkluzja bRI, należy zatem wykazać inkluzję przeciwną. Niech aR. Istniają zatem takie q, rR, że a = qb + r. Ponieważ v(b) jest minimalne, r = 0, czyli zachodzi równość a = qb, tj. abR, co dowodzi inkluzji IbR.

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}\big[\tfrac{1+\sqrt{19}{\rm i}}{2} \big].

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, bR \ {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ść rk + 1 =0. Dla najmniejszego takiego k reszta rk jest największym wspólnym dzielnikiem elementów a, bR. 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[edytuj | edytuj kod]

Pierścieniami Euklidesa są:

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