Magia liczb pierwszych doc


Magia liczb pierwszych.

Liczbą pierwszą nazywamy taką liczbę naturalną, która ma tylko dwa dzielniki: 1 i samą siebie. Ta prosta definicja niespodziewanie okazała się matematyczną żyłą złota, niewyczerpaną do dzisiaj.

Liczby pierwsze zastanawiały już starożytnych. W zasadzie nie da się chyba zajmować teorią liczb bez otarcia się o liczby pierwsze. Starożytni mieli już dobre pojęcie o tym, że każdą liczbę naturalną można przedstawić jako iloczyn pewnych liczb pierwszych i że rozkład ten jest jednoznaczny. Jest to tzw. Podstawowe twierdzenie arytmetyki, z którego wynika, że liczby pierwsze to swego rodzaju cegiełki służące do budowania innych liczb naturalnych.. Nie było sprawą oczywistą ile jest liczb pierwszych. Euklides jako pierwszy udowodnił, że w istocie jest ich nieskończenie wiele. Dowód jego jest bardzo prosty i elegancki, warto go przytoczyć:

Załóżmy, że jest skończenie wiele liczb pierwszych, dajmy na to n - rozumował Euklides - Oznaczmy je następująco: p1, p2, p3 ,... pn Rozważmy, zatem liczbę W= p1 *p2 *p3 *...* pn +1 Żadna z liczb p1, p2, p3 ,... pn nie jest dzielnikiem liczby W ( bo jest dzielnikiem liczby W-1). Zatem muszą istnieć jeszcze inne liczby pierwsze będące dzielnikami liczby W (być może samo W jest pierwsze), co oczywiście przeczy temu, że liczb pierwszych jest skończenie wiele. Wniosek? Jest ich nieskończenie wiele.

Sprawa nadal wydaje się całkiem prosta. Liczb naturalnych jest nieskończenie wiele, co więc dziwnego w tym, że akurat liczb pierwszych też jest nieskończenie wiele? Problem leży nie tyle w ich ilości, ale rozmieszczeniu, i sposobie stwierdzenia czy dana liczba jest pierwsza, a z tym już jest zdecydowanie trudniej. Łatwo jesteśmy wstanie wypisać pierwszych kilkanaście liczb pierwszych: 2,3,5,7,11,13,17,19,23... ale już, gdy przychodzi do liczb trzycyfrowych zaczynają się problemy. Z pomocą kartki papieru czy kalkulatora stwierdzimy szybko, że np. 509 to liczba pierwsza a 1001 złożona (7*11*13). Co jednak zrobimy, gdy przyjdzie nam (z bliżej nieokreślonych przyczyn) badać złożoność liczby 12345667788834151 (która tak na marginesie jest pierwsza). Czy istnieje jakiś prosty sposób? Czy da się jakoś określić rozmieszczenie liczb pierwszych tak, aby je łatwiej znajdować, wreszcie czy istnieje prosty wzór, który będzie je produkował? Odpowiedzi na te pytania okazują się być zaskakująco trudne, i sięgają daleko w głąb matematyki.

Co wiemy?
Wypisanie kilku małych liczb pierwszych od razu nakazuje szukać innych wśród liczb nieparzystych (jedyną parzystą liczbą pierwszą jest 2). Dalsze próby znalezienia prostego schematu spełzają jednak na niczym. Rozmieszczenie liczb pierwszych wydaje się być zupełnie chaotyczne! Wszelkie wymyślane sposoby bardzo szybko są obalane przez jakiś kontrprzykład. Wiadomo, że liczby pierwsze nie następują jedna po drugiej (z wyjątkiem 2 i 3), niektóre jednak dzieli odstęp równy 2 (np. 3 i 5, 5 i 7, 11 i 13, 6797727*215328-1 i 6797727*215328+1 itp.). Nazywamy je liczbami pierwszymi bliźniaczymi. Czy jest ich nieskończenie wiele? Niewiadomo. Wiadomo, że szereg ich odwrotności jest zbieżny, co oznacza, że występują dość rzadko, ale to oczywiście nie oznacza, że jest ich skończenie wiele. Z drugiej strony wiemy, że odległości między dwoma kolejnymi liczbami pierwszymi mogą być dowolnie duże. Przykład : każda liczba w postaci n!-k gdzie 1<k<n+1 ( ! oznacza silnię, a więc iloczyn wszystkich liczb naturalnych mniejszych równych od danego n. n!=1*2*3*4*...*n) jest złożona ( wystarczy wyciągnąć k przed nawias by się o tym przekonać). Oznacza to, że po liczbie n!-n-1 zawsze występuje co najmniej n-1 liczb złożonych. Zatem liczba 101!-101 to pierwsza z kolei 100 liczb złożonych poprzedzających liczbę 101!-1. n!±1 może być liczbą pierwszą (ale nie musi), więc wykluczamy k=1. Wniosek? Takie ubogie w liczby pierwsze pola mogą być dowolnie duże. W praktyce przykład ten pokazuje jedynie sposób dowiedzenia tego faktu, gdyż dziś wiadomo, że przerwy pomiędzy liczbami pierwszymi równe n występują zazwyczaj już dużo szybciej niż po (n+1)!-n-2...

Niektóre liczby w postaci 2p-1 są pierwsze (gdzie p jest liczbą pierwszą). Nazywamy jest liczbami pierwszymi Mersena (na cześć ich badacza). Są one szczególe gdyż stosunkowo łatwo się sprawdza czy dana liczba Mersena jest pierwsza. Stąd największa znana liczba pierwsza jest zazwyczaj liczbą Mersena. Czy jest ich nieskończenie wiele? Niewiadomo... Odpowiedź "niewiadomo" pojawia się zaskakująco w tych zakamarkach matematyki gdzie królują liczby pierwsze...

Rozmieszczenie
Jak się zatem zabrać do szacowania rozmieszczenia liczb, o których tak mało wiemy? Od czegoś trzeba zacząć! Na początek zdefiniujmy pewną ważną funkcję: y=0x01 graphic
. Jest to funkcja, której wartością jest ilość liczb pierwszych mniejszych lub równych od zadanego x (UWAGA - nie ma ona nic wspólnego z liczbą pi !), będziemy ją nazywać funkcją zliczającą liczby pierwsze. Spróbujmy zobaczyć jak zachowuje się jej wykres. Wiemy na pewno, że jest ona rosnąca i monotoniczna. Wiemy też, że rośnie wolniej od funkcji y=x (liczb pierwszych nie może być więcej niż wszystkich liczb naturalnych!). Spodziewamy się zatem że będzie to w przybliżeniu krzywa podobna do wykresu funkcji 0x01 graphic
. Okazuje się, że nasza funkcja rośnie szybciej niż pierwiastek z x, ale wolniej niż y=x/2 (zatem liczby pierwsze stanowią mniej niż połowę wszystkich liczb naturalnych, ale więcej niż pierwiastek). Trzeba gdzie indziej szukać dobrych oszacowań tej funkcji. Gauss słusznie nazywany księciem matematyków w wieku 15 lat (!) przypuszczał, że funkcja 0x01 graphic
jest asymptotyczna* do funkcji 0x01 graphic
(gdzie ln to logarytm naturalny). Dowód tego twierdzenia jest trudny (zostało udowodnione dopiero pod koniec XIX wieku), jest ono jednak dość ważnym krokiem w drodze do okiełznania liczb pierwszych i ma specjalną nazwę: Twierdzenie o liczbach pierwszych.

Troszkę lepiej niż 0x01 graphic
funkcję zliczającą liczby pierwsze przybliża tzw. logarytm całkowy (Rys. 1). Definiujemy go tak:

0x01 graphic


(To również podejrzewał Gauss)
Niestety zarówno jedno jak i drugie oszacowanie zapewnia jedynie asymptotyczność. Oznacza to, że nie są one użyteczne przy określaniu dokładnej wartości funkcji . Zdecydowanie lepsze oszacowanie podał w 1860 roku znakomity matematyk Bernhard Riemann. Skorzystał on w tym celu z niezwykłych właściwości pewnej niepozornej funkcji, o której grzechem byłoby nie wspomnieć.

Funkcja Dzeta
Klasyczną funkcję Dzeta (Rys. 2) eksploatował już Euler dowodząc, że liczb pierwszych jest nieskończenie wiele. Podał też kilka oszacowań, prawdziwą wartość tej, niepozornej na pierwszy rzut oka, funkcji odkrył jednak dopiero Riemann. Klasyczną funkcję Dzeta definiujemy tak:

0x01 graphic


dla x>1

Chciałoby się teraz powiedzieć: co taka funkcja ma do licha wspólnego z liczbami pierwszymi? Wbrew pozorom ma i to dużo. Sądzę, że czytelnicy, dla których matematyka nie ma wielu tajemnic szybko dojdą do tego, że funkcję Dzeta możemy równoważnie zapisać tak:

0x01 graphic



Gdzie iloczyn przebiega po wszystkich liczbach pierwszych (!). Ale na tym powiązania się nie kończą. Riemann wkopał się dalej w to matematyczne złoże i zapragnął rozszerzyć funkcję Dzeta na wszystkie liczby zespolone (zabieg taki zwany przedłużeniem analitycznym ma nieraz znakomite znaczenie przy badaniu funkcji. Niekiedy właściwości funkcji które normalnie są niezrozumiałe stają się oczywiste po rozszerzeniu na liczby zespolone). Sięgamy tu już na matematyczne głębiny, więc radzę wstrzymać oddech. Rozszerzoną funkcję Dzeta (Rys. 3,4) (zwaną od tej pory funkcją Dzeta Riemanna) definiujemy tak:

0x01 graphic



dla dowolnych 'z' zespolonych.
Prezentuje tu ten wzór nie po to, aby odstraszyć wszystkich potencjalnie zainteresowanych zagadnieniem, ale po to, aby ukazać niezwykle piękną złożoność teorii liczb. Mając tą funkcję, Riemann mógł przystąpić do szacowania rozmieszczenia liczb pierwszych. W tym celu potrzebował jeszcze jedną funkcję: R(x) (tzw. funkcję Riemanna), zdefiniowaną dość łatwo następującym wzorem:

0x01 graphic



i udowodnił poniższy wzór (co nie jest, jak zresztą widać, bynajmniej zadaniem trywialnym), który w sposób bardzo dokładny określa rozmieszczenie liczb pierwszych:

0x01 graphic



Sumowanie przebiega po wszystkich nie trywialnych (czyli zespolonych) zerach funkcji Dzeta Riemanna... No właśnie! I tu pojawia się problem. Jak znaleźć wszystkie nie trywialne zera funkcji Dzeta? To już zupełnie inna historia...

O nie trywialnych zerach funkcji Dzeta wiemy całkiem dużo, niestety zbyt mało, aby oszacowanie Riemanna okazało się szczególnie użyteczne. Wiemy, że jest ich nieskończenie wiele, i że ich zbiór jest przeliczalny. Wiemy, że są symetryczne względem osi rzeczywistej. Wiemy, że wszystkie leżą w tzw. pasie krytycznym (fragment płaszczyzny zespolonej o części rzeczywistej spełniającej nierówność 0<Re<1). Wiemy, że wszystkie odkryte do tej pory zera (a jest ich grubo ponad miliard) leżą na jednej prostej zwanej prostą krytyczną (prosta o części rzeczywistej równej 1). Riemann przypuszczał, że wszystkie leżą na tej prostej (co świadczy o niezwykłej intuicji tego genialnego matematyka). Jest to sławna hipoteza Riemanna, która gdyby się okazała prawdziwa mogłaby odegrać niesłychany wpływ na rozwój matematyki. Niestety od ponad 100 lat jest nietknięta i nie zanosi się żeby ktoś ją szybko udowodnił... Udało się, co prawda uzyskać kilka interesujących wyników (np. że przynajmniej 2/5 wszystkich zer leży na prostej krytycznej), do formalnego dowodu jednak daleko. Można jedynie w tym momencie zachęcić czytelników! Ten, kto udowodni hipotezę Riemanna zdobędzie sławę na wieki (oraz milion dolarów - jeśli jest to bardziej kusząca nagroda). Jest to problem jak się wydaje jeszcze o wiele większego kalibru niż udowodnione niedawno wielkie twierdzenie Fermata...

Wzory
A co ze wzorami produkujący łatwo i szybko liczby pierwsze? Niestety sprawa w tym względzie nie wygląda najlepiej. Zagadnieniem tym zajmował się Euler i odkrył kilka ciekawostek. Na przykład wielomian:

0x01 graphic


Po podstawieniu n=0,1,2,3,...39 produkuje liczby pierwsze 41, 43, 47, 53, 61, 71, 83, 97, 113, 131, 151, 173, 197, 223, 251, 281, 313, 347, 383, 421, 461, 503, 547, 593, 641, 691, 743, 797, 853, 911, 971, 1033, 1097, 1163, 1231, 1301, 1373, 1447, 1523, 1601.
Wynik ten jest dość elegancki i ma szerokie powiązania z tzw. Liczbami Heegnera. Ostatecznie dzisiaj znamy setki podobnych wzorów, które produkują ileś tam liczb pierwszych. Niektóre z tych wzorów zwracają nawet n-tą liczbę pierwszą po podstawieniu n. Wszystko to jednak w bardzo ograniczonym zakresie. Istnieją też przykłady wzorów wypisujących wszystkie liczby pierwsze w kolejności (są jednak absolutnie bezużyteczne gdyż korzystają z wartości funkcji , którą aby obliczyć trzeba najpierw znać wszystkie liczby pierwsze mniejsze od danej liczby, i tu kółko się zamyka...). Wzoru z prawdziwego zdarzenia, praktycznego, który byłby wstanie łatwo wyprodukować same liczby pierwsze nie ma!

Słowo na koniec

W tak króciutkim tekście trudno wymienić nawet połowę wszystkich zagadnień związanych z liczbami pierwszymi, a co dopiero udowodnić i nacieszyć się nimi. Prawdopodobnie, aby tego dokonać potrzebna by była księga o grubości ponad 2000 stron... Mam jednak nadzieje, że ten krótki tekst zachęci do poszukiwań w tej dziedzinie (a jest to naprawdę niezły kawałek matematycznego tortu). Przykładem może być tu chociażby sprawa ostatnio dość popularna, mianowicie kryptografia z kluczem publicznym, możliwa do praktycznego zaimplementowania jedynie dzięki pewnym sympatycznym własnością potęg modularnych o wykładnikach będących liczbami pierwszymi... Zapewniam, że gdy bardziej się wgłębić w teorię liczb, to działanie algorytmów kryptograficznych (np. RSA) wydaje się trywialnie (albo raczej genialnie) proste...

Obrazki

Rys 1.

0x01 graphic



Porównanie funkcji zliczającej liczby pierwsze z logarytmem całkowym. Podobieństwo jak widać jest całkiem niezłe.

Rys 2.

0x01 graphic



Wykres klasycznej funkcji Dzeta wygląda całkiem niepozornie, przypomina trochę gałąź hiperboli.

Rys 3.

0x01 graphic



Wykres modułu funkcji Dzeta Riemanna na płaszczyźnie zespolonej. Szczególnie interesująca jest linia x= 1/2. Tam właśnie występują nie trywialne miejsca zerowe. Ciekawostką może być, iż niedawno odkryto powiązanie w rozmieszczeniu zer funkcji Dzeta z pewnym rozkładami prawdopodobieństwa spotykanymi w fizyce!

Rys 4.

0x01 graphic



Powiększony fragment wykresu funkcji Dzeta Riemanna. Ponad miliard odkrytych za pomocą komputera miejsc zerowych spełnia hipotezę Riemanna i leży na prostej krytycznej. Czy wszystkie ją spełniają? To jeden z największych nierozwiązanych problemów matematycznych.


Bibliografia

"Księga liczb" - John H. Convay, Richard K. Guy
"The Riemann Hypothesis and Hilberts Tenth Problem" - S.Chowla



Wyszukiwarka

Podobne podstrony:
ppj - wypisywanie liczb pierwszych w javie, Do nauki, Pytania, rozwiązania, prace
ICM Gęstość rozmieszczenia liczb pierwszych w ciągu liczb naturalnych
Tablica liczb pierwszych i rozkładów na czynniki pierwsze, 04. chomikowe różności, Królowa matematyk
Magia liczb
ppj - wypisywanie liczb pierwszych w javie, Do nauki, Pytania, rozwiązania, prace
PIERWS~1 (5) DOC
PIERWS 1 DOC
PIERWS~1 (3) DOC
Sekret Liczby Dnia Urodzin (Magia Liczb)
Błocka Małgorzata Magia liczb, a piramidy egipskie
1000 liczb pierwszych
PIERWS~1 (2) DOC
labor pierwszy doc
Halina Poświatowska Pytasz czemu pociąga mnie magia liczb

więcej podobnych podstron