276062013

1.2. NWD i NWW w Z 3

Ustalmy dwie liczby całkowite a, b G Z*. Przyjmijmy: r_i := a, ro := \b\.

Krok 1: Zgodnie z algorytmem dzielenia z resztą (1.3.(B) (•)) istnieją liczby całkowite 5i,ri € Z takie, że:

(1)    a = r__: = ?i|6|+ri,

(2)    0 ^ n < \r₀\ = |6|.

Jeśli ri = 0, kończymy algorytm. Jeśli r\ ^ 0, to wykonujemy Krok 2.

Krok 2: Istnieją liczby całkowite ę₂, r₂ G Z :

(1)    r₀ = q₂ri + r₂,

(2)    0 < r₂ < rj < |r₀| = |6|.

Jeśli r₂ = 0, to kończymy algorytm. Jeśli r₂ ^ 0, to kontynuujemy analogicznie.

Ogólnie, mając rj_₂,rj_i takie, że r,_i 7^ 0, wykonujemy kolejny krok:

Krok (i>l): Istnieją liczby całkowite qi,r, G Z:

(1)    rj_₂ = ftri-i + rj,

(2)    0 ^    < r»_i.

Ze względu na nierówności: 0 ^ r* < r,_i istnieje AT(a, ó) G N takie, że 7^,jv(a,6)+1 — 0 ale ^N(o,6) 7^Ł 0.

Liczbę A^(a, 6) G N będziemy nazywać dalej długością algorytmu dla liczb a i b, (długość może być równa zero, gdy 6|a), zaś r(a, b) := rpjfuM wynikiem tego algorytmu.

W tak opisanym algorytmie r(a, b) jest największym wspólnym dzielnikiem liczb a, b. Z dowodem tego faktu zapoznać się można np. w C.l. Jest to jednak dla nas krok pomocniczy, celem jest udowodnienie tożsamości Bacheta-Bezouta. 1.2.4

Warto w tym momencie zwrócić uwagę na jeden fakt, który znajdzie swoje uogólnienie w teorii pierścieni. Nie bez przyczyny przypominamy znany algorytm Euklidesa tak dokładnie. Przyglądając się bowiem uważnie przebiegowi algorytmu zauważymy, że reszty pojawiające się w każdym kroku spełniają zależność: |rj+i| < |r*|, słowem za każdym razem obniżana jest wartość funkcji | • | dla reszty. W przyszłości będziemy chcieli prześledzić taki sam algorytm w pierścieniach (gdzie w analogii do dodawania i mnożenia liczb będziemy mieć zadane w pewien sposób ’dodawanie ’ i ’mnożenie ’ elementów) tzw. euklidesowych, zastępując moduł wartością pojawiającej się tam funkcji ą>. Zauważymy wówczas, że w taki sam jak wyżej sposób będziemy mogli znaleźć NWD elementów pierścienia euklidesowego, (choć należy zwrócić uwagę na różnicę w definicji tych pojęć w sensie algebraicznym i w sensie teorioliczbowym). Studiując teorię pierścieni euklidesowych warto wrócić do dowodów przedstawianych poniżej i zauważyć, iż możemy je przeprowadzić w analogiczny sposób w sytuacji algebraicznej.

Twierdzenie 1.2.3. Z: a,b G Z*

T. (1) r(a,b) = NWD(a,b),

(2) Istnieją liczby k, l G Z takie, że r(a,b) = ka + lb, (szczególny przypadek identyczności Bacheta-Bezouta 1.2.4■