276061999

Podstawy teorii liczb

Twierdzenie 1.4.5 (Zasadnicze twierdzenie arytmetyki). C.j Każda niezerowa liczba całkowita, nie będąca jednością w Z posiada jednoznaczny rozkład na iloczyn liczb pierwszych.

Dowód. Wystarczy oczywiście wykazać twierdzenie dla liczb naturalnych większych od jedynki. W naturalny sposób dowód rozbija się na dwie części: wykazanie istnienia rozkładu

1    wykazanie jego jednoznaczności.

Istnienie. Indukcja względem n: dla n = 2 teza jest spełniona.

Załóżmy tezę dla liczb naturalnych m takich, że 1 < m < n.

Jeśli n jest liczbą pierwszą, to dowód zakończony.

Jeśli n nie jest liczbą pierwszą, to n = ab, gdzie l<a<nil<6<n wobec tego z założenia indukcyjnego a i b są liczbami pierwszymi bądź iloczynami takich. Stąd również n jest iloczynem liczb pierwszych.

Jednoznaczność Ponownie indukcja względem n.

Dla n = 2 jednoznaczność rozkładu jest oczywista ze względu na pierwszość tej liczby. Gdyby bowiem było n = pi ■ ... ■ p_r gdzie p; 6 P i r > 1 to 2 musiałaby dzielić jedną z liczb Pi a tym samym być jej równa (wobec pierwszości). Wtedy dzieląc obie strony przez

2    mielibyśmy, że pozostałe Pj dzielą jedynkę co jest niemożliwe. Wobec tego r = 1 i p\ = 2.

Zakładając tezę dla liczb mniejszych lub równych (n — 1) gdzie n > 2 przypuśćmy, że dla n, mamy dwa rozkłady:

n = Pi •. • • • p_r = qi ■ • • • • q_s

gdzie pi, qj € V oraz p\ ^ ... ^ p_r, q\ sC ... ^ q_s. Oczywiście możemy przyjąć, że r > 1 w przeciwnym razie mamy do czynienia z liczbą pierwszą.

Niech p będzie najmniejszą liczbą pierwszą dzielącą n, skąd p dzieli Pi dla pewnego i, (1.4.2(2)) skąd p = Pi czyli z minimalności p mamy p = pi, analogicznie p = q\.

Niech teraz m - < n. Wobec tego mamy rozkład:

m = p₂ ■.. ■ • p_r = qi • • ■ ■ • q_s-

Z założenia indukcyjnego otrzymujemy r = s i istnieje bijekcja a zbioru {2,..., n} na siebie, (permutacja tego zbioru) taka, że V i G {2,... ,r} Pi — q„(i)■ Przyjmując ct(1) — 1, <j{i) = a (i), dla i > 1 otrzymujemy poszukiwaną permutację zbioru {1,..., n}.    □

Twierdzenie 1.4.6 (Euklides). Istnieje nieskończenie wiele liczb pierwszych.

Dowód. Przypuśćmy dla dowodu niewprost, że V — {pi,... ,p_T}.

Przyjmijmy m := p\ • ... • p_r + 1. Żadne p, nie dzieli liczby m, (w przeciwnym razie dzieliłoby jedynkę). Niech p będzie liczbą pierwszą dzielącą m, (taka istnieje na mocy 1.4.5). Wobec tego p i p jest liczbą pierwszą, co prowadzi do sprzeczności.    □

W tej chwili istnieje całe multum dowodów nieskończoności zbioru wszystkich liczb pierwszych. Zaprezentowany powyżej dowód, w dość podobnej wersji jak w Elementach jest