22872

2

3 ALGORYTM EUKLIDESA

Twierdzenie 2.1 (Twierdzenie Euklidesa.) Zbiór liczb pierwszych jest nieskończony.    ■

Znacznie więcej na temat lieznośd zbioru liczb pfcrwszych mówi twierdzenie udowodnione przez Eulera² w 1718 roku. Twierdzenie to podajemy tu bez dowodu odsyłając zainteresowanych do (?), udzie można znaleźć nie tylko dowód tego twierdzenia, ale także rozważania na temat rozmieszczenia liczb pierwszych (por. także }?]).

Twierdzenie 2.2 (Euler 1738) Szereg Yl_r. j» “ jest rozbieżny.

3 Algorytm Euklidesa

Poniższe twierdzenie o dzieleniu liczb całkowitycłi powinno być doskonale znane.

Twierdzenie 3.1 (O dzieleniu liczb całkowitych.) Dla dowolnych liczb całkowitych a i b. b > 0. istnieją jednoznacznie wyznaczone liczby q,r € Z takie.

że

(1)

a = bq + r

przy czyni 0 < r < b.

Dowód. Zdefiniujmy liczbę q wzorem q = mnx{</ € Z : bq' < a). Łatwo zauważyć, że nasze q jest dobrze określone (to znaczy istnieje dla dowolnych a.b całkowitych takich, że b > 0).

Niech r = a — bq. Wykażemy, że tak zdefiniowane liczby całkowite q i r spełniają warunki twierdzenia.

Rzeczywiście, r jest nieujemne i równość (1) jest oczywista. Należy jednak sprawdzić, że r < b. Zauważmy, że gdyby r > b. wówczas prawdziwe byłyby związki

bq<b(q + l) = bq + b<bq + r = a

Tak więc q + 1 spełniałoby b(q + 1) < a. co sprzeczne jest ze sposolx*m wyboru 11 jiiko największej liczby całkowitej dla której bq < a.

Pozostaje udowodnić, że q i r spełniające tezę twierdzenia są jedyne. Przypuśćmy, że a = bq\ + rj. a — bq₂ + r₂. przy czym 0 < rj.r₂ < b. Wówczas prawdziwa byłaby równość

bq\ + n = bq-i + r₂

a więc

b(q2 ~ <li) = H - r₂

A więc rj — r₂ byłoby krotnością b. Ponieważ jednak |rj — r₂| < 6, rj — r₂ jest równe zeru, a więc n = r₂. Stąd otrzymujemy, że b(q₂ - t/i) = 0, co wobec

³Iycoiii>r<l Euler, 1707-1783.