276062012

2 Podstawy teorii liczb

Pozostaje jedynie pytanie, czy r < |&|. Udowodnimy tę część niewprost. Gdyby r ^ |6|, to r — |6| 5= 0 oraz r — |6| — a — qb — \b\ = a — (q + sgn(b))b, więc r — |b| G S oraz r — \b\ < r, (skoro b 0 to |6| to co najmniej 1), sprzeczność z wyborem r.

Jednoznaczność reszty nieujemnej

Przypuśćmy, (dla dowodu niewprost) że a — bq\ +rj — bq% +r2, 0 ^ r\ < |6|, 0 ^ r2 < \b\ i niech np. r\ < r%, czyli q\ — q<i ^ 0. Wtedy b(qi — 52) = r2 — r\ i mamy: |6| ^ |&||?i — 92I = |r*2 ^— ul = (^2 ^— n) < \b\ sprzeczność.    □

Zachęcam do udowodnienia we własnym zakresie drugiej części twierdzenia 1.1.4.

1.2 NWD i NWW w Z

W szkole średniej spotkaliśmy się z pewnością z pojęciem największego wspólnego dzielnika i najmniejszej wspólnej wielokrotności. Przypomnimy tu więc znaną definicję w wersji teorioliczbowej. Trzeba jednak pamiętać, że odpowiednie pojęcia w wersji algebraicznej definiowane będą nieco inaczej ze względu na podstawowy problem: rozważając struktury algebraiczne nie możemy na ogól mówić pojęciu "najmniejszy”, czy "największy”, musimy przy definicjach uciekać się do innych własności.

Definicja 1.2.1 (NWD, NWW, względna pierwszość). (•) Największym wspólnym dzielnikiem liczb a\,...,a_r € Z, (zakładamy, że przynajmniej jedna z liczb jest niezerowa) nazywamy największą liczbę całkowitą, która dzieli wszystkie a\,... ,a_r. ¹ Oznaczenie : NWD(ai,..., o_r) (w literaturze również: (aj,..., a_r))

(•) Najmniejszą wspólną wielokrotnością niezerowych liczb całkowitych Oi,... ,a_r nazywamy najmniejszą liczbę całkowitą dodatnią, która jest podzielna przez każdą z liczb Oi,... ,a_r.

Oznaczenie : NWW(oi,..., a_r) (w literaturze również: [01,..., a_r])

(•) (liczby względnie pierwsze) Liczby a\,... ,a_r G Z, a\ 7^ 0 nazywamy względnie pierwszymi, gdy NWD(oi,... ,a_r) — 1.

Przypomnimy teraz jak można obliczać największy wspólny dzielnik. Rozważmy przypadek dwóch liczb: a, b G Z. Oczywiście, jeśli a G Z*, b = 0, to NWD(a, b) = |a|. Załóżmy więc, że obie liczby są niezerowe i przypomnijmy algorytm służący do wyliczania wówczas NWD. Choć omawiany niżej algorytm nie jest algorytmem we współczesnym sensie tego słowa, to jednak zgodnie z tradycją zachował swą nazwę: algorytm Euklidesa. Więcej o algorytmie poczytać można w aneksie C.l

Uwaga 1.2.2 (Algorytm). ² Euklidesa³ dla liczb całkowitych.

(¹) Zauważmy, że stwierdzenie 'największa’ ma tutaj sens: rozważamy naturalny porządek w zbiorze liczb całkowitych, zaś potencjalne dzielniki są ograniczone z góry przez |a,|

(²) Nazwa algorytm pochodzi od brzmienia fragmentu nazwiska arabskiego matematyka Muhammada ibn Musa al.-Chorezmiego, którego uznaje się za prekursora metod obliczeniowych w matematyce. Żył on na przełomie VIII i IX wieku, przyczynił się do upowszechnienia systemu dziesiętnego oraz wprowadził stosowanie zera jako symbolu oznaczającego "nic”

(³) Euklides: matematyk grecki, głównie działający w Aleksandrii, (ok.364-300 p.n.e. dokładne daty nie są znane), autor jednego z najbardziej znanych dziel matematycznych: Elementy