Matematyka dyskretna 1/Wykład 10: Teoria liczb

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Wstęp

Teoria liczb jest dziedziną matematyki, zajmującą się badaniem własności liczb – początkowo tylko naturalnych. Obecnie należałoby powiedzieć: głównie naturalnych. Jej początki sięgają starożytności. Zajmowali się nią Pitagoras, Euklides, Eratostenes, Diofantos i wielu innych. Bujny rozwój teorii liczb datuje się mniej więcej od czasów działalności Pierre'a Fermata (1601-1665), autora wypowiedzi słynnego Wielkiego Twierdzenia Fermata. Do dwudziestego wieku powszechną była opinia, iż teoria ta nie ma żadnego zastosowania. Jednak dzięki wielkiemu rozwojowi kryptografii - nauki zajmującej się układaniem i łamaniem szyfrów - pogląd ten musiał zostać zweryfikowany.

W dwu kolejnych wykładach poznamy podstawowe pojęcia i klasyczne twierdzenia teorii liczb - niektóre pochodzące jeszcze z czasów starożytnych. Zainteresowanych zachęcamy do rozszerzenia swej wiedzy w kursie Matematyka Dyskretna 2, gdzie przedstawiony jest system kryptograficzny RSA, oparty na tych podstawowych faktach z teorii liczb.

Uwaga

W wykładach poświęconych teorii liczb wszystkie liczby są całkowite, chyba że wyraźnie jest powiedziane inaczej.

Uwaga

W wykładach dotyczących teorii liczb poznamy też kilka algorytmów operujących na liczbach naturalnych. Rozważając ich złożoność musimy poczynić kilka założeń o złożoności podstawowych operacji arytmetycznych. Długość liczby to liczba bitów , czyli liczba cyfr w zapisie binarnym (dwójkowym). Wynosi ona , ale nam wystarcza wiedzieć, że jest ona . Przyjmujemy, że złożoność dodawania liczb i jest proporcjonalna do sumy ich długości, dokładniej że jest oraz że złożoność mnożenia liczb i jest (choć znane są szybsze algorytmy).

Podstawowe pojęcia

Dowolną liczbę wymierną można wydzielić przez dowolną niezerową liczbę wymierną i wynik tego działania jest liczbą wymierną. Ograniczając sie jednak zbioru liczb całkowitych, nie każde dzielenie jest wykonalne: , ale ?. Rozważamy więc dzielenie liczb całkowitych z resztą.

Dzielenie liczb całkowitych z resztą.

Niech , wtedy dla każdej liczby całkowitej istnieją jednoznacznie wyznaczone: iloraz i reszta spełniające:



Resztę z dzielenia przez zapisujemy też jako: .

Przykład

, , , , . W pewnych sytuacjach reszta równa jest , np. .

dzieli (lub jest podzielne przez ), co zapisujemy , jeśli istnieje takie, że . W takim wypadku mówimy też, że jest dzielnikiem lub, że jest wielokrotnością . Innymi słowy, jeśli dzieli to reszta z dzielenia przez równa jest tzn. .

Obserwacja 10.1

Dla dowolnych zachodzi:

  • jeśli to ,
  • jeśli i to ,
  • jeśli , to .

Dowód

Z założenia pierwszego punktu wiemy, iż istnieje takie, że . Mnożąc obie strony równości przez dostajemy . A więc istnieje takie, że , co z kolei oznacza, że .

Z założenia drugiego punktu wiemy, iż istnieją takie, że i . Łatwo zauważamy, że dla mamy , czyli .

Z założenia trzeciego punktu istnieją takie, że i . Dodając stronami ostatnie równości otrzymujemy , czyli .

End of proof.gif

Największy wspólny dzielnik liczb i (zapisywany przez ), gdzie chociaż jedna z liczb jest różna od , to największa liczba taka, że i . Oczywiście, .

Przykład

, , .

Algorytm Euklidesa

Algorytm Euklidesa to algorytm wyznaczania największego wspólnego dzielnika dwu dodatnich liczb całkowitych. Warto tu wspomnieć, iż jest to jeden z najstarszych znanych algorytmów. Euklides zamieścił go ok. 300 roku p.n.e. w Elementach - jednym z najsłynniejszych dzieł naukowych ludzkości. Jednak sam algorytm prawie na pewno znał już Eudoksos z Knidos ok. 50 lat wcześniej.

  1. Wczytaj liczby .
  2. Oblicz jako resztę z dzielenia przez .
  3. Zastąp przez , zaś przez .
  4. Jeżeli to zwróć w przeciwnym wypadku przejdź do (2).

Przykład

Przebieg obliczenia :



Zgodnie z instrukcją (4) algorytm zwraca .

Applet1

Dowód

Dla dowódu poprawności algorytmu Euklidesa ustalmy dwie liczy naturalne . Jeśli to podany algorytm odwróci ich porządek przy pierwszym wykonaniu kroku (3), gdyż w tym przypadku . Zauważmy, że w każdym następnym kroku , ponieważ reszta z dzielenia przez leży w zbiorze . A zatem kolejne reszty będą tworzyć ciąg ściśle malejący, który w końcu osiągnie , czyli algorytm Euklidesa po pewnej skończonej ilości kroków się zatrzyma.

Pozostaje sprawdzić, czy algorytm Euklidesa zwraca właściwą odpowiedź. Niech tzn. dla pewnego . Wszystkie dzielniki i dzielą prawą stronę ostatniej równości, a więc dzielą też , co implikuje . Dowodzi to, iż wszystkie pary rozważane przez algorytm mają te same dzielniki, a więc ten sam .

End of proof.gif

Rozszerzenie algorytmu Euklidesa.

Poza znajdowaniem NWD dwóch podanych liczb algorytm Euklidesa można zastosować do wskazania dwu dodatkowych liczb takich, że



Już sam fakt, że istnieją takie liczby to obserwacja, która leży u podstaw wielu kolejnych twierdzeń. Ponadto rozszerzony algorytm Euklidesa jest intensywnie stosowany do rozwiązywania równań, w przekształceniach kryptograficznych.

Dowód

Załóżmy, że . Niech , , natomiast będą kolejnymi resztami wygenerowanymi przez algorytm Euklidesa, przy czym . Wtedy wiemy, że oraz



dla pewnych . Mamy zatem . Załóżmy indukcyjnie, dla , że istnieją takie, że . Ponieważ otrzymujemy:



A więc możemy zejść z liczbą do , co daje pożądane przedstawienie jako .

End of proof.gif

Czas działania.

Niech będą zdefiniowane, jak w dowodzie powyżej. Załóżmy dodatkowo, iż (jeśli nie, to zaczynamy analizować po pierwszym kroku algorytmu). Pokażemy, że



Jeśli , to natychmiast mamy . Załóżmy więc, że . W tym przypadku podczas dzielenia przez zachodzi , czyli .

Ponieważ po każdych, kolejnych dwu krokach rozmiar spada co najmniej dwukrotnie, kroków jest . W każdym kroku przeprowadzane jest dzielenie liczb długości , a więc operacji bitowych. To oznacza, iż do policzenia () algorytmem Euklidesa wystarcza operacji bitowych.

Aby policzyć współczynniki , takie, że , zgodnie z przedstawionym dowodem, należy przedstawić jako kombinację i , a później pozbyć się kolejnych (poczynając od ) wprowadzając . Mamy więc kroków i w każdym kroku przeprowadzamy mnożenie i dodawanie lub odejmowanie liczb o długości co najwyżej .

Przykład

Działanie rozszerzonego algorytmu Euklidesa dla i .



A więc . Aby wyrazić jako kombinację danych wejściowych liczymy:



Applet2.svg

Liczby pierwsze

Każda liczba ma przynajmniej dwa dodatnie dzielniki: oraz .

Liczba pierwsza to liczba naturalna posiadająca dokładnie dwa różne dzielniki. W szczególności .

Przykład

Oto lista wszystkich liczb pierwszych mniejszych od :



Liczba złożona to liczba naturalna , która nie jest pierwsza, a więc ma jakiś dodatni dzielnik różny od i .

Liczby względnie pierwsze to takie liczby i , dla których , co zapisujemy inaczej jako .

Przykład

  • bo ,
  • bo ,
  • bo .

Wspomniane Elementy Euklidesa zawierają słynny lemat:

Lemat 10.2 [Lemat Euklidesa]

Jeśli i , to .

Dowód

Ponieważ , to istnieją takie, że . Mnożąc obie strony równości przez otrzymujemy:



Z założenia wiemy, iż dzieli lewą stronę powyższej równości. Musi zatem dzielić też prawą.

End of proof.gif

Obserwacja 10.3 [Rozkład na iloczyn liczb pierwszych]

Każdą liczbę można przedstawić jako iloczyn liczb pierwszych.

Dowód

Intuicyjnie, wystarczy rozkładać liczby złożone w iloczynie, aż wszystkie będą liczbami pierwszymi, na przykład



Dla formalnego dowodu załóżmy niewprost, iż istnieje liczba naturalna większa od , nierozkładalna na iloczyn liczb pierwszych. Korzystając z Zasady Minimum, weźmy najmniejszą taką liczbę . Musi to być liczba złożona, gdyż dowolna liczba pierwsza jest jednoelementowym iloczynem liczb pierwszych. A zatem jest złożona i istnieją takie, że . Ale wtedy oraz są mniejsze od , więc z minimalności , rozkładają się na iloczyn liczb pierwszych. Ale wtedy także byłoby iloczynem liczb pierwszych, co przeczy temu, że jest nierozkładalna i kończy dowód.

End of proof.gif

Nietrywialnym faktem jest, że każda liczba jest jednoznacznie rozkładalna na iloczyn liczb pierwszych (z dokładnością do kolejności liczb w iloczynie). Fakt ten powszechnie znany jest jako Fundamentalne Twierdzenie Arytmetyki. Dowód tego twierdzenia w dużej części był już w Elementach Euklidesa, jednak pierwszy, pełny i poprawny dowód przedstawił Carl Friedrich Gauss.

Twierdzenie 10.4 [Fundamentalne Twierdzenie Arytmetyki]

Każda liczba naturalna ma jednoznaczny (z dokładnością do kolejności liczb w iloczynie) rozkład na iloczyn liczb pierwszych.

Dowód

Podamy dwa dowody tego twierdzenia.

Najpierw przedstawimy dowód pochodzący od Euklidesa. Niech będzie najmniejszą liczbą naturalną posiadającą dwa różne rozkłady na liczby pierwsze: , gdzie oraz . Żadna z liczb nie może pojawić wśród (i na odwrót), gdyż wydzielając obie strony przez , otrzymalibyśmy mniejszą liczbę z dwoma różnymi rozkładami. Liczba pierwsza dzieli pierwszy iloczyn, a więc też dzieli i drugi:



Zauważmy, że



gdyż są to dwie, różne liczby pierwsze. Na mocy Lematu Euklidesa otrzymujemy, iż . Kolejno możemy wyeliminować pozostałe liczby z prawego iloczynu dochodząc do , oczywistej sprzeczności.

A oto alternatywny dowód. Niech będzie najmniejszą liczbą naturalną większą od posiadającą dwa różne rozkłady na liczby pierwsze: , gdzie oraz . Tak, jak poprzednio dostajemy, że żadna liczba pierwsza nie może być jednocześnie w obu rozkładach. Bez straty ogólności niech . Wtedy istnieje takie, że



gdzie ( nie może być równe , gdyż oznaczałoby to iż ). Wymnażając obie strony równości przez otrzymujemy



Drugi składnik w prawej stronie tej równości musi być zatem liczbą naturalną. Oznaczając ją przez mamy więc



Wartość obu stron powyższej równości jest mniejsza od , gdyż . Ponieważ , to po rozłożeniu liczby na czynniki pierwsze dostaniemy dwa różne rozkłady liczby mniejszej od , co przeczy założeniu o minimalności .

End of proof.gif

Fundamentalne Twierdzenie Arytmetyki eksponuje znaczenie liczb pierwszych. Okazuje się, że są to podstawowe bloki, z których można zbudować w unikalny sposób dowolną liczbę naturalną większą od .

Przykład

, , , .

Problem faktoryzacji.

Obecnie nie jest znany żaden efektywny algorytm faktoryzujący liczby naturalne, tzn. znajdujący rozkład na iloczyn liczb pierwszych. Oczekiwana trudność tego problemu jest sercem wielu współczesnych systemów kryptograficznych (np. RSA). Nie wszystkie liczby są równie trudne w rozkładzie. Póki co, (w połowie 2006 roku) najtrudniejsze wydają się liczby, które są iloczynami dwu liczb pierwszych podobnej długości.

Przykład

Aby choć trochę zrozumieć trudność problemu faktoryzacji proponujemy znaleźć nietrywialny dzielnik liczby złożonej . Na stronie WWW firmy RSA podane są znacznie większe liczby, za rozkład których RSA skłonna jest płacić nawet 200 tys. USD.

Znajomość rozkładu liczby na czynniki pierwsze pozwala określić, w sposób systematyczny, wszystkie jej dzielniki.

Obserwacja 10.5

Jeśli jest rozkładem liczby na iloczyn liczb pierwszych, to każdy jej dzielnik jest postaci , dla pewnych .

Dowód

Załóżmy, dla dowodu niewprost, że w rozkładzie liczby występuje liczba pierwsza, powiedzmy , która nie występuje w rozkładzie . Oczywiście , bo . Ponieważ i są dwiema różnymi liczbami pierwszymi, to na mocy Lematu Euklidesa otrzymujemy . W podobny sposób możemy wyeliminować kolejno liczby dochodząc do sprzeczności, że . A więc rozkład liczby zawiera wyłącznie liczby pierwsze z rozkładu liczby, czyli , przy czym oczywiście wszystkie są nieujemne, ale niektóre mogą być zerowe. Pozostaje pokazać, że . Załóżmy, że dla pewnego . Wtedy



przy czym liczba ma w swoim rozkładzie czynnik , a liczba nie ma. To jednak stoi w sprzeczności z ustanowionym wcześniej faktem, że wszystkie czynniki rozkładu każdego dzielnika jakiejkolwiek liczby naturalnej występują w rozkładzie tego dzielnika.

End of proof.gif

Ponieważ ciągów liczb naturalnych spełniających jest dokładnie z Obserwacji 10.5 dostajemy natychmiast:

Wniosek 10.6

Jeśli jest rozkładem liczby na iloczyn liczb pierwszych, to liczba ma dokładnie dodatnich dzielników.

Przykład

{

Innym natychmiastowym wnioskiem z Obserwacji 10.5 jest:

Wniosek 10.7

Dla jeśli , i , to .

Mając dany rozkład liczb i możemy błyskawicznie policzyć .

Obserwacja 10.8

Jeśli , i , gdzie , to



Dowód

Każdy wspólny dzielnik jest postaci , przy czym oraz . Oczywiście wśród liczb tej postaci, liczba jest największa.

End of proof.gif

Oczywiście mając rozkłady liczb na czynniki pierwsze łatwo jest już policzyć . Jak jednak odnotowaliśmy uzyskanie takich rozkładów nie jest łatwe. Dzięki algorytmowi Euklidesa potrafimy jednak (efektywnie) znaleźć NWD dwóch liczb bez znajomości ich rozkładu.

Ważnym dualnym pojęciem do NWD jest pojęcie najmniejszej wspólnej wielokrotności dwu liczb.

Najmniejsza wspólna wielokrotność dwu liczb (oznaczana przez ) to najmniejsza liczba dodatnia taka, że i .

Znając rozkłady dwu liczb możemy, analogicznie do NWD , wyznaczyć ich NWW.

Obserwacja 10.9

Jeśli , i , gdzie , to



Na podstawie ostatnich dwu obserwacji dostajemy natychmiast:

Wniosek 10.10

Wniosek ten można wykorzystać do szybkiego liczenia NWD dwu liczb bez znajomości ich rozkładów na czynniki pierwsze. Wyznaczywszy najpierw algorytmem Euklidesa wartość , wystarczy potem podzielić


Jak dużo jest liczb pierwszych?

Już Euklides odnotował, że "jest więcej liczb pierwszych niż w każdym danym zbiorze liczb pierwszych", tzn.:

Twierdzenie 10.11

Liczb pierwszych jest nieskończenie wiele.

Dowód

Podamy dwa dowody tego twierdzenia pochodzące odpowiednio od Euklidesa i Eulera.

Załóżmy niewprost za Euklidesem, że liczb pierwszych jest skończenie wiele i są to: . Rozważmy liczbę . Jest ona oczywiście większa od każdej . Ponadto żadna z liczb pierwszych nie dzieli , bo przy dzieleniu przez daje resztę . A zatem , albo jest nową liczbą pierwszą, albo w rozkładzie są nowe liczby pierwsze. Sprzeczność.

Również dowód Eulera jest dowodem niewprost. Załóżmy więc, że zbiór wszystkich liczb pierwszych jest skończony. Zauważmy, że:



Istotnie, pierwsza równość wynika ze wzoru na sumę nieskończonego ciągu geometrycznego: każdy czynnik iloczynu po lewej jest sumą nieskończonego ciągu geometrycznego o ilorazie . Druga równość jest konsekwencją Fundamentalnego Twierdzenia Arytmetyki. Ponieważ założyliśmy, że liczb pierwszych jest skończenie wiele, to lewa strona równości jest oczywiście skończona. Wiemy natomiast, że suma po prawej stronie jest nieograniczona, jako że sumy częściowe początkowych wyrazów tego ciągu to kolejne liczby harmoniczne .

End of proof.gif

Matematycy zastanawiali się także, czy liczby pierwsze są, w pewnym sensie, regularnie rozłożone wśród liczb naturalnych. Jest wiele ciekawych rezultatów opisujących ten rozkład.

Twierdzenie 10.12 [Dirichlet 1837]

Dla dowolnych dwu dodatnich i względnie pierwszych liczb istnieje nieskończenie wiele liczb postaci dla .

Przykład

Twierdzenie Dirichleta uogólnia wiele wcześniej znanych faktów. Dla przykładu, możemy wywnioskować, iż jest nieskończenie wiele liczb pierwszych postaci ():



jak i postaci ():



Tezę kolejnego twierdzenia, znanego jako Twierdzenie Bertanda-Czebyszewa lub Twierdzenie Czebyszewa, postawił Joseph Bertrand w 1845 roku. Zweryfikował on poprawność swojej tezy dla liczb z przedziału . Pełny dowód przestawił dopiero Pafnuty Czebyszew w 1850 roku. Dowód, który tu przedstawiamy pochodzi od Paula Erd{o}s'a. Wykorzystał on następującą funkcję

gdzie oznacza zbiór liczb pierwszych nie większych od . Ważną własność tej funkcji opisuje następujący lemat.

Lemat 10.13

Dla zachodzi



Dowód

Dla dowodu indukcyjnego odnotujmy najpierw, że oraz .

Niech teraz będzie parzyste. Wtedy oczywiście nie jest liczbą pierwszą i mamy



Niech więc będzie nieparzyste, czyli dla pewnego . Rozważmy liczbę



Zauważmy, że każda liczba pierwsza w przedziale dzieli . Rzeczywiście, żadna liczba z mianownika nie może skrócić liczby pierwszej w liczniku co oznacza, że jest w rozkładzie . Ponadto, łatwo oszacować od góry przez , np. w ten sposób:



To z kolei pozwala nam oszacować następująco:



Z założenia indukcyjnego mamy natomiast , czyli



End of proof.gif

Twierdzenie 10.14 [Czebyszew 1850]

Dla dowolnego istnieje liczba pierwsza taka, że .

Dowód

Dla dowodu niewprost załóżmy, że jest najmniejszą liczbą , dla której nie ma żadnej liczby pierwszej w przedziale . Jeśli , to jedna z liczb pierwszych będzie pomiędzy a . Oznacza to, że .

Przeanalizujmy teraz rozkład na czynniki pierwsze liczby:



Najpierw jednak zauważmy, że ponieważ a liczba jest największym składnikiem tej sumy, to:



Ponieważ jest największym czynnikiem licznika , to wszystkie liczby pierwsze w rozkładzie są mniejsze od . Niech , gdzie jest liczbą pierwszą, będzie największą liczbą taką, że . Innymi słowy, jest potęgą liczby w rozkładzie .

Łatwo zauważyć, że ma czynnik w swoim rozkładzie na czynniki pierwsze razy. To implikuje, że



Każdy składnik tej sumy postaci może przyjąć wartość:

  • , jeśli część ułamkowa jest mniejsza od ,

lub

  • , jeśli część ułamkowa jest niemniejsza od .

Ponadto, dla wszystkie składniki zerują się, bo . To pozwala na następujące oszacowanie liczby



To z kolei daje zaskakującą nierówność



Z dotychczasowych ustaleń dotyczących rozkładu liczby na czynniki pierwsze wiemy, że nie występują tam liczby pierwsze takie, że:

  • , gdyż jest największym czynnikiem w liczniku rozważanego symbolu Newtona,
  • , gdyż założyliśmy, że nie ma takich liczb pierwszych,
  • , gdyż wtedy (ponieważ ) i wobec tego tylko pierwszy składnik w nieskończonej sumie wyznaczającej może być niezerowy. Ale wtedy i tak .

Zatem wszystkie liczby pierwsze w rozkładzie są niewiększe niż . Liczby pierwsze występują tam w co najwyżej pierwszej potędze, jako że . Z kolei iloczyn przebiegający po liczbach pierwszych można oszacować z góry przez . Dotychczasowe oszacowania dają nam więc



Z Lematu 10.13 wiemy, że , więc



Ponieważ mamy



Z kolei , bo , więc



Logarytmując obie strony nierówności otrzymujemy



Podstawmy . Wtedy , a więc , co w stoi sprzeczności z , gdyż



End of proof.gif

Paulowi Erd{o}s'owi udało się uogólnić Twierdzenie Bertranda-Czebyszewa na kilka sposobów. Pokazał on np., że:

  • dla każdego istnieje takie , że dla wszystkich istnieje przynajmniej liczb pierwszych w przedziale ,
  • dla dowolnej liczby naturalnej , między liczbami a znajdują się co najmniej dwie liczby pierwsze – co najmniej jedna postaci oraz co najmniej jedna postaci .

Wszystkie obserwacje o pewnej regularności rozkładu liczb pierwszych w zbiorze liczb naturalnych potwierdza (i w pewnym sensie uogólnia) Twierdzenie o Liczbach Pierwszych. Niech, jak poprzednio, będzie zbiorem liczb pierwszych niewiększych od oraz .

Twierdzenie 10.15 [Twierdzenie o Liczbach Pierwszych]



Twierdzenie o Liczbach Pierwszych opisuje asymptotyczną gęstość liczb pierwszych wśród liczb naturalnych. Z grubsza, mówi ono, iż wybierając losowo liczbę w pobliżu pewnej dużej liczby , mamy szansy na to, by wylosowana liczba była pierwsza. Dla przykładu: w pobliżu mniej więcej co -ta liczba jest pierwsza, tymczasem w pobliżu już co -wsza liczba jest pierwsza. A więc, statystycznie, w przedziale jest znacznie więcej liczb pierwszych niż mówią poprzednie twierdzenia. Problem polega na tym, że choć wiemy, że musi ich być bardzo dużo, to nie jesteśmy w stanie udowodnić, że dla konkretnie rozważanej liczby nie nastąpiło jakieś "lokalne zaburzenie".

Twierdzenie o Liczbach Pierwszych sformułował Adrien-Marie Legendre'a w 1796. Zostało ono udowodnione niezależnie przez Hadamarda i de la Vallée Poussina w 1896. Dowód używa złożonych metod analitycznych, wykraczających poza ramy tego wykładu. Dlatego nie przedstawimy jego pełnego dowodu. W zamian pokażemy znacznie słabsze:

Twierdzenie 10.16

.

Dowód

Lemat 10.13 mówi, że , co równoważnie można wyrazić jako



Ponieważ w oczywisty sposób , to ze wzoru Stirlinga mamy:



Logarytmując stronami otrzymujemy , co implikuje .

End of proof.gif

Sito Eratostenesa

Jak wyznaczyć wszystkie liczb pierwszych niewiększych od ? Jeszcze w czasach starożytnych Eratostenes opisał metodę postępowania rozwiązującą ten problem.

Algorytm Sita

  1. Wczytaj . Wypisz listę wszystkich liczb naturalnych od do . Na początku wszystkie liczby są nieskreślone.
  2. Dopóki istnieje nieskreślona jeszcze liczba na naszej liście niewiększa od powtarzaj:
    Weź pierwszą nieskreśloną liczbę z listy i dodaj do zbioru znalezionych liczb pierwszych. Później skreśl liczbę z listy i skreśl wszystkie wielokrotności liczby , które są jeszcze na liście.
  3. Wszystkie pozostałe, nieskreślone liczby z listy dodaj do zbioru znalezionych liczb pierwszych.

Wystarczy wykreślać wielokrotności liczb pierwszych, niewiększych od , gdyż jeśli dowolna liczba ma nietrywialny dzielnik (różny od 1 i niej samej), to ma nietrywialny dzielnik pierwszy, niewiększy od .

Applet3.svg