Liczby Pierwsze

Liczby pierwsze są to takie liczby naturalne, które większe są od jedynki i podzielne bez reszty przez samą siebie i jedynkę. Jednym z pytań dotyczących liczb pierwszych, które narzuca się każdemu jest pytanie o liczbę tych liczb: ile ich jest, skończenie wiele czy, wręcz przeciwnie, nieskończenie? Na to akurat znamy odpowiedź od czasów starożytnych: liczb pierwszych jest nieskończenie wiele. Wiedział o tym już w IV w. p.n.e. sam wielki Euklides. Innymi słowy, nie istnieje największa liczba pierwsza: dla każdej danej liczby pierwszej możemy znaleźć większą. Istotnie, gdyby była jedynie skończona liczba liczb pierwszych (np. P) to iloczyn wszystkich tych P liczb, zwiększony o jedynkę, musiałby być też pierwszy (bo przy dzieleniu przez którąkolwiek z tych P liczb dawałby oczywiście. resztę jeden); zatem przypuszczenie, że jest ich P, jest fałszywe, bowiem znaleźliśmy oto następną.





Ta dość prosta konstrukcja daje również teoretycznie przepis na konstruowanie coraz większych liczb. Np. 2*3*5+1=31; 31 jest liczbą pierwszą. Nietrudno spostrzec , że ten przepis ma też wady. Nie można nim otrzymać np.: 11,13,17,19,...); po drugie omówiony powyżej zapis konstruowanej liczby trudno uznać za przejrzysty. Dodam jeszcze, że w ogóle nie istnieje - i nie może istnieć - żaden "wzór", w zwykłym sensie tego słowa który by "produkował" wszystkie liczby po kolei. Nie oznacza to, iż nie można podać wzorów, które dają nam całą serię takich liczb, dowolnej zresztą długości. Skoro liczb pierwszych jest nieskończenie wiele, to może do odnajdywania kolejnych przyda się inny algorytm.





Należy wziąć jakąś liczbę i dzielić ją przez liczby od niej mniejsze których jest prawdopodobnie skończenie wiele jeśli wszystkie liczby podzielą ją z reszty to znaczy że jest to liczba pierwsza. Pomimo że ten algorytm jest poprawny to jest jeszcze bardzo nie efektowny gdyż przy dużych liczbach nawet komputery mogą się pomylić (mowa tu o liczbach posiadających setki tysiące cyfr).





Istnieje jeszcze sposób rozkładania liczby na czynniki pierwsze zwany faktoryzacją polega ona na rozłożeniu liczby na liczby pierwsze (np. 15=3*5, 100=5*5*2*2). Jeśli liczbę da się w taki sposób rozłożyć to nie jest to liczba pierwsza. Ten sposób jest jeszcze bardziej nieefektowny od poprzedniego.





Bardzo starym i znanym sposobem jest “sito Eratostenesa” wypisuje się dowolnej długości ciąg liczb naturalnych zaczynając od dwójki np.: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25... z którego najpierw wykreślamy liczby podzielne przez 2 oprócz dwójki i tak zostaje nam: 2, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25..... następnie przez trzy (bez trójki), przez pięć (bez piątki) zostaje nam 2, 3, 5, 7, 11, 13, 17, 19, 23. I to już mamy same liczby pierwsze mniejsze od dwudziestu pięciu. Biorąc dostatecznie długi ciąg wyjściowy i wykonując czysto mechaniczne eliminowanie (łatwe dla komputera) co drugiej, co piątej i tak dalej “odsiejemy” w efekcie wszystkie liczby pierwsze.





Ta prosta metoda zawodzi jednak w wypadku ogromnej długości i przy jej zastosowaniu obliczenia trwały zbyt długo, żeby ten zachęcający algorytm uznać za przydatny.





W jaki sposób znaleźć więc wielkie liczby pierwsze. Używając niezwykle potężnych i piekielnie drogich superkomputerów Cray z serii T90, wyposażone w potężny algorytm Lucasa-Lehmera. Patent na użycie Craya do wyszukiwania kolejnych liczb pierwszych ma przede wszystkim wchodząca w skład specjalnego zespołu Silicon Graphic’s Cray Research sławna para matematyków David Slowinski – Paul Gage. Szczególnie Slowinski uważany jest za “łowcę” wielkich liczb pierwszych. Ten program jest ważny nie tylko dlatego, że bije rekordy, ale i dlatego, iż jest on cennym narzędziem do testowania każdego nowego modelu superkomputera. Techniki, stosowane do przyspieszenia działania programu wyszukiwania liczb pierwszych, mają duże znaczenie dla rozwiązywania niezwykłej wagi problemów, w rodzaju obliczania pewnych prognoz pogody czy analizy danych, służących poszukiwaniu nowych złóż ropy.





Inny od użycia superkomputera sposób poszukiwania liczb pierwszych polega na zebraniu kilkudziesięciu czy kilkuset przyjaciół i wykonanie tej pracy zespołowo, przy podziale jej na mniejsze fragmenty. Dokładnie na tym polega projekt GIMPS (Great Internet Mersenne Prime Search), w ramach Którego Joel Armengaud Jako pierwszy, odkrył nową liczbę pierwszą Mersenne’a: 2ⁿ-1 gdzie n=1398269 ( liczby Mersenne’a są to liczby które da się zapisać w postaci 2ⁿ-1 gdzie n musi być liczbą pierwszą; niektóre z nich też są pierwsze. Liczby Mersenne’a dość łatwo poddają się testowaniu). Dokonał tego, używając opracowanego przez George’a Woltmana modyfikacji algorytmu Lucasa-Lehmera i pracując wspólnie z ponad 700 matematykami, komunikującemu się przez Internet. Obecnie w projekcie GIMPS bierze udział już około 2 tysięcy entuzjastów liczb pierwszych. Założyli sprawdzenie wszystkich liczb Mersenne’a o wykładniku mniejszym niż 1345000 jeszcze przed końcem 1997 roku, a do końca 2000 roku chcą sprawdzić wykładniki aż do 2655000. Z początkiem 1996 roku sam Woltman dołączył do zespołu GIMPS. 23 listopada 1996 znaleziono liczbę pierwszą o 420921 cyfrach i jest największą znaną liczbą pierwszą Mersenne’a (35 z kolei) i największą liczbą pierwszą w ogóle.





Liczby pierwsze Mersenne’a są też szczególnie ważne dla kryptografów. Profesor Richard Crandall, szef zespołu badawczego firmy NeXT, opatentował w swoim czasie system szyfrowania znany jako Fast Elliptic Encryption (Szybkie Kodowanie Eliptyczne), wykorzystujący właśnie te liczby. Program, który odnalazł rekordową liczbę, został oparty na wynikach badań Crandalla, które zagwarantowały z górą dwukrotnie szybszy niż dotychczas przebieg obliczeń.





Poszukiwania liczb pierwszych Mersenne’a nadal trwają. Do projektu GIMPS dołączyć może każdy, kto ma komputer i dostęp do Internetu. Całe oprogramowanie dostajemy na stronie internetowej, wraz ze wszystkimi wskazówkami.





Oto adres internetowy: http://ourworld.compuserve.com/homepages/justforfun/prime.htm .





Warto zwrócić uwagę na jeszcze jedno: otóż, choć odkryta została liczba 35 liczba Mersenne’a to jeszcze nie znamy wszystkich poprzednich; nie wiemy mianowicie, czy pierwsze są liczby 31 – 34. A oto kolejna ciekawostka: znajomość którejś z liczb Mersenne’a oznacza automatycznie, iż pewna znacznie od niej większa liczba zasługuje na miano doskonałej, tzn. jest równa sumie swych mniejszych od niej dzielników np.: najmniejszą liczbą doskonałą jest 6=1+2+3 kolejne to 28, 496, 8128. Znał je już Euklides. Otóż w związku z omawianym odkryciem od listopada 1996 wiemy, że 2ⁿ - 1 gdzie n=1398268 zaś od sierpnia 1997 roku liczba 2ⁿ - 1 gdzie n=2976221.











Największe znane dotychczas liczby pierwsze





Liczba


Cyfr


Rok odkrycia


Odkrywcy





2ⁿ-1 n=21701


6533


1968


L.C. Noll (i Laura Nickel)





2ⁿ-1 n=23209


6987


1979


L.C. Noll





2ⁿ-1 n=44497


13395


1979


David Slowinski (i Harry Nelson)





2ⁿ-1 n=86243


25962


1982


David Slowinski





2ⁿ-1 n=132049


39751


1983


David Slowinski





2ⁿ-1 n=216091


65050


1985


David Slowinski





391981*2ⁿ-1 n=216193


65087


1989


L.C. Noll, J. Brown, S. Zarantonello





2ⁿ-1 n=756839


227832


1992


David Slowinski, Paul Gage





2ⁿ-1 n=859433


258716


1994


David Slowinski, Paul Gage





2ⁿ-1 n=1257787


378632


1996


David Slowinski, Paul Gage




















Czego jeszcze nie wiemy o liczbach pierwszych?








Nie wiemy, czy istnieje nieskończenie wiele liczb doskonałych. Nie wiadomo również czy istnieje choćby jedna doskonała liczba nieparzysta.





Liczbami bliźniaczymi nazywamy dwie liczby pierwsze, różniące się od siebie o 2 (jak 3 i 5, 5 i 7, 11 i 13, 17 i 19...). Nie wiadomo, czy jest ich skończenie, czy nieskończenie wiele.





Liczby pierwsze w postaci p, p+2, p+6, p+8 nazywa się czworaczkami (np.: 5,7,11,13; 11,13,17,19; 101,103,107,109...). Nie wiemy, czy jest ich skończenie, czy nie skończenie wiele.





Liczbami zaprzyjaźnionymi nazywamy dwie liczby naturalne m i n o tej własności, że suma wszystkich mniejszych od m dzielników tej liczby równa jest n i jednocześnie suma wszystkich mniejszych od n dzielników liczby n równa jest m. Oczywiście, każda liczba doskonała jest zaprzyjaźniona sama ze sobą. Najmniejszą parę liczb zaprzyjaźnionych stanowią 220 i 284. Znanych jest około 8 tysięcy takich par; nie wiadomo, czy jest ich nieskończenie wiele. Nie znamy również żadnej takiej pary, w której jedna liczba byłaby parzysta, a druga nieparzysta.