Liczby Pierwsze

Liczby pierwsze to liczby naturalne, większe od jeden oraz dzielące się (bez reszty) przez siebie samą oraz jedynkę. Najciekawszym pytaniem, jeżeli chodzi o liczby pierwsze, jest pytanie o ich ilość. Czy jest ich skończenie wiele, czy może nieskończenie wiele? Odpowiedz na to pytanie istnieje od czasów starożytności. Starożytni wiedzieli, że jest ich nieskończenie wiele. Wiedział o tym również Euklides w IV wieku przed naszą erą. Czyli wiemy już, że nie istnieje największa liczba pierwsza, czyli dla dowolnej liczby pierwszej możemy znaleźć liczbę pierwszą, która będzie od niej większa.

Ponieważ gdyby było skończenie wiele liczb pierwszych (dajmy na to P) to ich iloczyn powiększony o jeden też musiałby być liczbą pierwszą, ponieważ gdy podzielimy go przez dowolną liczbę P ze składowych iloczynu dawałby reszty jeden.. Czyli mamy, że przypuszczenie, że liczb pierwszych jest P jest fałszywe, ponieważ znaleźliśmy następną, różną od poprzednich.

Dzięki tej konstrukcji mamy przepis, jak konstruować coraz większe liczby.

Przykład:

2*3*5+1=31 31 to liczba pierwsza.

Jak widać, konstrukcja ta ma również wady. Dzięki niej nie da się otrzymać: 11,13,17,19,...i tak dalej. Patrząc na zapis tej konstrukcji, od razu dostrzeżemy, że nie jest on przejrzysty. Nie istnieje przecież żaden wzór, dzięki któremu można by opisać taką konstrukcję i żeby z niego uzyskać wszystkie kolejne liczby.

Popatrzmy na pewien algorytm, który produkuje liczby pierwsze:

Weźmy dowolną liczbę i zacznijmy ją dzielić przez liczby, które są od niej mniejsze, jest ich pewnie skończenie wiele. Jeżeli wszystkie takie liczby podzielą z resztą, oznacza to, że jest ona liczbą pierwszą.

Ten algorytm jest dosyć dobry, ale przy bardzo dużych liczbach, łatwo o pomyłkę.

Innym algorytmem, polegającym na rozkładaniu liczby na liczby pierwsze jest faktoryzacja.

Przykład faktoryzacji:

15=3*5 100=5*5*2*2

Jeśli liczbę można przedstawić w taki właśnie sposób to nie jest ona liczbą pierwszą, ale ten sposób jest sposobem jeszcze bardziej nieefektywnym niż wcześniejszy.

Aby znaleźć wszystkie liczby pierwsze, które nie są większe od z góry zadanej liczby n, można się posłużyć następującym sposobem, zwanym "sitem Eratostenesa". Należy wypisać w porządku wszystkie liczby naturalne od 2 do n. Pierwsza z tych liczb jest liczbą pierwszą. Zostawiamy ją i następnie wykreślamy wszystkie liczby, które dzielą się przez dwa, a ponieważ się dzielą przez dwa to nie są pierwsze. W praktyce oznacza to, że wykreślamy wszystkie parzyste liczby. Jeśli to już zrobimy, pierwszą liczbą po 2 jest 3. Jest ona liczbą pierwszą. Zostawiamy ją i następnie wykreślamy wszystkie liczbą, które dzielą się przez 3. Po tej operacji, kolejną liczbą, która nie została wykreślona jest 5. Jest ona liczbą pierwszą, więc ją zostawiamy i wykreślamy z pozostałych wszystkie te, które dzielą się przez 5. Jeśli będziemy kontynuować to wykreślanie w ten sposób otrzymamy wszystkie liczby pierwsze mniejsze od liczby n.

Niestety i ta metoda nie jest najlepsza. Przy bardzo dużych liczbach, obliczenia trwają zbyt długo, aby stosować go na dłuższą metę.

Najlepszym sposobem znajdowania liczb pierwszych jest posługiwanie się komputerem Cray z serii T90, wyposażonym w algorytm Lucasa-Lehmera. Sławni matematycy: David Slowinski - Paul Gage posiadają patent na posługiwanie się nim. Slowinski jest uważany za "łowcę" największych liczb pierwszych.

Liczby Mersenne'a

Liczby postaci 2p-1, przy czym p to liczba pierwsza. Przyjmujemy, że p = 2, 3, 5, 7 wtedy otrzymamy liczby pierwsze Mersenne'a. Zaś 211-1=2047=23*89 jest złożona. Nie wiemy, czy pośród liczb Mersenne'a mamy nieskończenie wiele liczb pierwszych, ani nawet czy pośród nich możemy wskazać największą znaną liczbę pierwszą. Największą, jaką dzisiaj znamy liczbę pierwszą Mersenne'a, jest liczba 2216091-1, która w dziesiętnym rozwinięciu ma 65050 cyfr. Jeżeli znajdziemy nową liczbę pierwszą Mersenne'a, tym samym odkrywamy nową parzystą liczbę doskonałą

Poza używaniem superkomputera innym sposobem na znajdowanie liczb pierwszych jest zebranie działanie zespołowe komputerów połączonych przez Internet. Na takim pomyśle oparty jest projekt GIMPS (Great Internet Mersenne Prime Search). W jego ramach Joel Armengaud odkrył, jako pierwszy pierwszą liczbę Mersenne'a: 2ⁿ-1 gdzie n=1398269. Odbyło się to przy użyciu zmodyfikowanego algorytmu Lucasa-Lehmera, który opracował George Woltman i komunikacji Internetowej około 700 matematyków.

Liczby pierwsze Mersenne'a ważne są dla kryptografów. Profesor Richard Crandall to szef badawczego zespołu firmy NeXT. Opatentował on system szyfrowania zwany Fast Elliptic Encryption (Szybkie Kodowanie Eliptyczne), przy wykorzystaniu tych właśnie liczby.

Badania nad poszukiwaniem liczb pierwszych Mersenne'a trwają nadal. Do GIMPS może dołączyć każdy posiadający komputer oraz dostęp do Internetu. Niezbędne oprogramowanie pobiera się ze strony internetowej, razem ze wskazówkami.

adres internetowy strony: http://ourworld.compuserve.com/

Świat liczb pierwszych jest wciąż fascynujący dla matematyków. Zaskakująca jest liczba pierwsza złożona z samych jedynek, np. taka posiadająca 23 cyfry: 11 111 111 111 111 111 111 111. Część liczb pierwszych zapisana jest kolejnymi cyframi jak choćby: 23, 67, 89, 789, 456, 23456789, 1234567891. Znowu inne to palindromy, czyli liczby "symetryczne" np.: 11, 757, 111181111. Wyróżniamy także liczby lustrzane jak.: 13 i 31, 37 i 73, 79 i 97, 113 i 311.

Największe znane 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

Informacje, jakich jeszcze nie mamy na temat liczb pierwszych:

Nie udowodniono jeszcze, czy liczb doskonałych jest nieskończenie wiele. Nie wiemy nawet czy istnieje jakaś liczba doskonała nieparzysta.

Liczby bliźniacze to takie 2 liczby pierwsze, które różnią się tylko od siebie o 2

Przykład:

3 i 5 5 i 7 11 i 13 17 i 19

Nie wiemy, czy jest ich nieskończenie wiele.

Liczby pierwsze postaci p, p+2, p+6, p+8 nazywamy czworaczkami.

Przykład:

5,7,11,13 11,13,17,19 101,103,107,109

Nie wiemy, czy jest ich nieskończenie wiele.

Liczby zaprzyjaźnione to takie 2 naturalne liczby m i n, które mają następującą własność:

suma wszystkich dzielników tej liczby, które są mniejsze od m jest równa n oraz równocześnie suma wszystkich dzielników tej liczby, które są mniejsze od n jest równa m.

Jak można się domyślić, wszystkie liczby doskonałe są zaprzyjaźnione same ze sobą.

Najmniejsza para liczb zaprzyjaźnionych to: 220 i 284.

Dzielnikami właściwymi liczby 220 są liczby:

{1,2,4,5,10,11,20,22,44,55,110} stąd 1+2+4+5+10+11+20+22+44+55+110=284

Dzielnikami właściwymi liczby 284 są:

{1,2,4,71,142} stąd 1+2+4+71+142=220

Innym przykładem liczb zaprzyjaźnionych są liczby 1184 i 1210.

Znamy około 8 tysięcy par takich jak powyższa, ale nie wiemy, czy jest takich nieskończenie wiele.

Nie znamy także ani jednej takiej pary, dla której jedna z liczb byłaby nieparzysta, a druga parzysta.