Liczba pierwsza –
liczba naturalna
, która ma dokładnie dwa
dzielniki
naturalne:
jedynkę
i siebie samą, np.
-
2
,
3
,
5
,
7
,
11
,
13
,
17
,
19
,
23
,
29
,
31
,
37
,
41
,
43
,
47
,
53
,
59
,
61
,
67
,
71
,
73
,
79
,
83
,
89
,
97
, itp.
Zbiór wszystkich liczb pierwszych oznacza się symbolem . Liczby naturalne większe od 1, które nie są pierwsze, nazywa się
liczbami złożonymi
. Z podanych definicji wynika, że liczby
0
i
1
nie są ani pierwsze, ani złożone[1].
Podstawowe własności
- Najmniejszy różny od jedynki dzielnik liczby naturalnej większej od jedności jest liczbą pierwszą.
-
Euklides
pokazał, że żaden skończony zbiór nie zawiera wszystkich liczb pierwszych:
- Niech X będzie skończonym zbiorem liczb pierwszych. Niech x będzie iloczynem wszystkich liczb występujących w X (gdy X jest puste, to x=1). Jedynym wspólnym dzielnikiem liczb x oraz x+1 jest 1. Zatem żadna liczba pierwsza, występująca w X, nie jest dzielnikiem liczby x+1. Ale x+1 > 1. Więc x+1 ma dzielnik p, który jest liczbą pierwszą. Liczba pierwsza p nie należy do X (bo jest dzielnikiem liczby x+1).
- Każda liczba naturalna większa od 1 daje się jednoznacznie zapisać w postaci iloczynu skończonego niemalejącego ciągu pewnych liczb pierwszych. Twierdzenie to był w stanie udowodnić już Euklides (stworzył niezbędne narzędzia), ale uczynił to dopiero
Gauss
. Twierdzenie to oznacza, że liczby pierwsze są w pewnym sensie atomami, z których przy pomocy mnożenia zbudowane są pozostałe liczby.
Wyznaczanie
Aby znaleźć wszystkie liczby pierwsze w zadanym przedziale liczbowym można posłużyć się algorytmem
sito Eratostenesa
: jeśli liczba naturalna N większa od 1 nie jest podzielna przez żadną z liczb pierwszych nie większych od pierwiastka z N, to N jest liczbą pierwszą.
Natomiast metoda, która daje odpowiedź na pytanie czy dana liczba naturalna jest pierwsza, czy nie – nosi nazwę
testu pierwszości
. Wśród takich metod praktyczne zastosowanie mają testy probabilistyczne, to znaczy takie, które pozwalają określić pierwszość liczby z dostatecznie dużym prawdopodobieństwem np:
test pierwszości Millera-Rabina
,
test pierwszości Solovay-Strassena
.
Rozkład n! na czynniki pierwsze
Niech oznacza wykładnik, z którym liczba pierwsza p występuje w rozkładzie liczby naturalnej n. Wtedy
gdzie jest jedyną liczbą całkowitą, spełniającą nierówność
dla dowolnego rzeczywistego x. Liczbę nazywamy
częścią całkowitą
liczby rzeczywistej x. Powyższa suma jest skończona, gdyż tylko skończona liczba jej składników jest różna od 0 – mianowicie pierwsze wyrazów.
- Literatura: na przykład[2] – rozdział 7.0[3]; – rozdział 6.3, Twierdzenie 6.9.
Rozkład środkowego współczynnika dwumianowego
Zbadajmy . Oczywiście op(n) = 1, gdy liczba pierwsza p należy do przedziału . Ogólnie
Ponieważ
dla dowolnej liczby rzeczywistej x, to ze wzoru na, z poprzedniego fragmentu, wynika, że
Równość p(lnx) / (lnp) = x pozwala powyższą nierówność wyrazić równoważnie jako
czyli
Twierdzenie Jeżeli , to .
Prawdziwe jest także twierdzenie:
Twierdzenie Jeżeli n > 2 jest liczbą naturalną, oraz p – liczbą pierwszą z przedziału , to p nie jest dzielnikiem współczynnika .
Rozmieszczenie
Rozmieszczenie liczb pierwszych wśród liczb naturalnych spełnia pewne prawidłowości statystyczne, ale nie jest znany żaden wzór, który pozwalałby wyznaczać liczby pierwsze w sposób bardziej efektywny niż metoda Eratostenesa.
Kilka poniższych twierdzeń przybliża zagadnienia związane z badaniem rozmieszczenia liczb pierwszych na
osi liczbowej
.
Szereg odwrotności wszystkich liczb pierwszych
Niech oznacza zbiór liczb pierwszych.
Leonhard Euler
udowodnił, że
szereg liczbowy
odwrotności wszystkich liczb pierwszych jest
rozbieżny
. Sugeruje to, że liczby pierwsze nie mogą być rozłożone zbyt "rzadko" na osi liczbowej. Rozbieżność tego szeregu daje też nowy dowód na istnienie nieskończenie wielu liczb pierwszych.
Dowód twierdzenia Eulera
Niech
Ponieważ
- ,
to
- P(x) > Q(x) − 1
dla dowolnego naturalnego x. Wystarczy zatem dowieść, że Q(x) może być dowolnie wielkie.
Szereg geometryczny:
oraz rozkładalność liczb naturalnych na iloczyny liczb pierwszych, daje nierówność
Ale , a więc
- ,
zatem
gdy . Koniec dowodu.
Franz Mertens uzyskał podobne oszacowanie P(x) także od góry.
Oszacowania iloczynu odcinka liczb pierwszych
Jasnym jest, że zachodzi podzielność
Więc dla n > 1 otrzymujemy:
Powyższe współczynniki dwumianowe są składnikami sumy ze wzoru Newtona na (1 + 1)2n − 1. Są więc one mniejsze od 22n − 2 = 4n − 1 (ostro, bo w sumie Newtona występują też inne składniki). Tak więc mamy nasze pierwsze oszacowanie (od góry) iloczynu odcinka liczb pierwszych:
dla n > 2, a nawet dla każdego n > 1. Bardziej atrakcyjne byłoby oszacowanie iloczynu początkowego odcinka liczb pierwszych
Ale przynajmniej możemy powyższą nierówność przepisać w postaci
dla każdego n > 1. Oczywiście
dla każdego naturalnego n > 1.
- Twierdzenie
- dla każdej liczby całkowitej x > 1.
- Dowód
- Można sprawdzić bezpośrednio, że twierdzenie zachodzi dla x = 2,3.
Rozpatrzmy parzyste x > 3. Wtedy 1 < x / 2 < x. Możemy więc indukcyjnie założyć, że twierdzenie zachodzi dla x / 2. Zatem, korzystając ze wcześniejszego oszacowania iloczynu odcinka (niepoczątkowego), które zachodziło dla każdego x: = 2n > 2, otrzymujemy
Więc indukcja zachodzi dla parzystego przypadku. Dla nieparzystego x > 3 mamy , co pozwala nam stosować założenie indukcyjne dla (oraz znowu wcześniejsze oszacowanie):
Koniec dowodu
Uwaga Twierdzenie zachodzi dla każdej liczby rzeczywistej , a nie tylko dla całkowitych.
Postulat Bertranda – Twierdzenie Czebyszewa
Czebyszew
udowodnił następujące twierdzenie (patrz[2] – rozdział 9[3], – rozdział 6.9):
- Twierdzenie
Dla dowolnej liczby naturalnej n większej od 1, między liczbami n a 2n istnieje co najmniej jedna liczba pierwsza.
- Dowód
Wyżej zdefiniowaliśmy op(n) i odnotowaliśmy następujące trzy twierdzenia:
- Jeżeli , to ; albo krótko: .
- Jeżeli n > 2 jest liczbą naturalną, oraz p – liczbą pierwszą z przedziału , to p nie jest dzielnikiem wspólczynnika .
- dla każdego rzeczywistego x > 1.
Zdefiniujmy:
- .
Twierdzenia dowiedziemy pokazując, że .
Otóż L(n) = M(n)N(n), gdzie:
Dla x > 8 liczba liczb pierwszych nie większych od x jest mniejsza od . Zatem gdy n > 32, M(n) ma nie więcej, niż czynników, z których każdy jest ograniczony od góry przez 2n. Zatem
oraz
Z drugiej strony jest największym z 2n + 1 składników sumy Newtona przedstawiającej (1 + 1)2n = 4n, przy czym dwa składniki równe są 1. Więc
Przy tym nierówność jest ostra dla n > 1, a co dopiero dla n > 32. Dla takich n, nierówność , po obustronnym pomnożeniu przez 2n, wyniknie z
- ,
czyli
czyli, po zlogarytmowaniu:
Z tego, że dla x > 1 zachodzi ln(x) < x − 1, otrzymujemy dla n > 32, że
Wystarczy zatem dowieść
- ,
czyli
- .
Ponieważ , to wystarczy dowieść, że:
co dla jest równoważne z:
- n2 − 136n + 16 > 0
Nierówność ta zachodzi dla każdego . Więc twierdzenie zachodzi dla każdego . Dla twierdzenie zachodzi, gdyż kolejne liczby pierwsze w następującym ciągu są mniejsze od podwojonego poprzednika:
Koniec dowodu.
Dla dowolnej, nieujemnej liczby całkowitej k bez większego trudu można by dowieść nierówności
lub słabszej:
dla wszystkich , gdzie stała C zależałaby od k. Nierówność ta zapewniłaby k+1 liczb pierwszych pomiędzy n i 2n, dla wszystkich, dostatecznie dużych n (dla ).
Metoda Czebyszewa
Czebyszew wprowadził iloczyny odcinków kolejnych liczb naturalnych, i ich kombinacje iloczynowo-ilorazowe. Z jednej strony takie iloczyny dają się dokładnie szacować, a z drugiej, dobierając starannie ich kombinacje, uzyskuje się iloczyny w których gęsto jest od kolejnych liczb pierwszych w potędze 1.
Metodę Czebyszewa uprościł (Sznirelmana[2])
Srinivasa Ramanujan
, który skupił się na środkowym współczynniku dwumianowym, czyli na (2n)!, podzielonym dwukrotnie przez n!. Działa to dobrze w przypadku postulatu Bertranda, ze względu na odcinek pomiędzy daną liczbą naturalną i dwukrotnie większą. Jednak Czebyszew uzyskał mocniejszy wynik, gdyż zamiast proporcji 2 wystarczyła mu dowolnie ustalona powyżej 6/5 (patrz[3]). Udowodnione po Czebyszewie twierdzenie o rozmieszczeniu liczb pierwszych natychmiast daje podobny wynik dla wszelkich proporcji ustalonych powyżej 1.
Wariacja Erdősa
Paul Erdős
wzmocnił twierdzenie Czebyszewa dowodząc
- Twierdzenie
Dla dowolnej liczby naturalnej n > 6, między liczbami n, a 2n, znajdują się co najmniej dwie liczby pierwsze – co najmniej jedna postaci 4k + 1, oraz co najmniej jedna postaci 4m + 3.
Twierdzenie Dirichleta
Poniższe twierdzenie zostało udowodnione przez
Dirichleta
- Twierdzenie
W dowolnym
ciągu arytmetycznym
liczb naturalnych: a, a + q, a + 2q, a + 3q, ... takim, że a i q są
względnie pierwsze
, występuje nieskończenie wiele liczb pierwszych. (Przy ustalonym q, ilość liczb pierwszych dla różnych a, względnie pierwszych z liczbą q, jest w pewnym asymptotycznym sensie taka sama.)
Przypadki szczególne
- Ciąg arytmetyczny liczb naturalnych :
- Niech A będzie niepustym zbiorem skończonym liczb naszego ciągu. Niech X będzie ich iloczynem. Wtedy 6X − 1 nie może mieć dzielniki pierwsze wyłącznie dające resztę 1 z dzielenia przez 6 (ich iloczyn dałby resztę 1). Zatem istnieje taki dzielnik pierwszy p | 6X − 1, że . Dzielnik ten nie należy do A, czyli żaden taki zbiór skończony nie zawiera wszystkich liczb pierwszych z naszego ciągu arytmetycznego, a więc takich liczb pierwszych jest nieskończenie wiele.
Uwaga Ciąg arytmetyczny liczb naturalnych zawiera powyższy, ale ma tylko jedną więcej liczbę pierwszą, mianowicie 2.
- Ciąg arytmetyczny liczb naturalnych :
- Dowód, że ten ciąg zawiera nieskończenie wiele liczb pierwszych podobny jest do wcześniejszego, powyżej, dla przypadku mod 6. Taki prosty dowód działa tylko dla reszty -1, i tylko mod n :=3 lub 4 lub 6, kiedy to jedynymi resztami mod n, względnie pierwszymi z n, są liczby -1 oraz 1 (mod n).
- Ciąg arytmetyczny liczb naturalnych :
- Euler pokazał, że nieparzysty dzielnik pierwszy liczby naturalnej postaci a2 + 1 musi dać resztę 1 z dzielenia przez 4. Niech więc A będzie niepustym zbiorem skończonym liczb naszego ciągu. Niech X będzie ich iloczynem. Wtedy (2X)2 + 1 musi mieć dzielnik pierwszy z naszego ciągu. Ale dzielnik taki nie może należeć do A, co oznacza, że zbiór wszystkich liczb pierwszych w naszym ciągu jest nieskończony.
Twierdzenie o liczbach pierwszych
Podstawowe twierdzenie o rozmieszczeniu liczb pierwszych wśród liczb naturalnych sformułował
Gauss
, który na podstawie badań empirycznych zasugerował, że liczba π(n) liczb pierwszych w
przedziale
[1, n] opisana jest zależnością
gdzie symbol Li(n) oznacza
resztę logarytmu całkowego
, a "~" oznacza równość asymptotyczną rozumianą jako
Rozwinięcie logarytmu całkowego w szereg daje oszacowanie:
Gauss nie udowodnił tego twierdzenia – dopiero pod koniec XIX wieku zostało ono udowodnione przez
Hadamarda
i de la Vallee Poussina.
Najprostszą postacią przybliżenia funkcji π jest pierwszy element tego szeregu:
W tym wypadku także zachodzi asymptotyczna równość:
Hipoteza Riemanna
Rozmieszczenie liczb pierwszych na osi jest też związane bezpośrednio z hipotezą Riemanna. Mianowicie, jest ona równoważna stwierdzeniu, że
liczba π(n)
liczb pierwszych w przedziale [1, n] wyraża się wzorem:
gdzie użyto
notacji dużego O
.
Hipoteza liczb pierwszych bliźniaczych
Według tej teorii
liczb pierwszych bliźniaczych
jest nieskończenie wiele.
Szczególne rodzaje liczb pierwszych
Liczby pierwsze bliźniacze
Liczby pierwsze p i q są
bliźniacze
jeśli p = q + 2. Przykłady: 3 i 5, 5 i 7, 11 i 13, 17 i 19, 29 i 31, 41 i 43, 59 i 61, 71 i 73...
5 jest bliźniacza zarówno z 3 jak i z 7.
Nie wiadomo, czy istnieje nieskończenie wiele bliźniaczych liczb pierwszych.
Największa znana para liczb pierwszych bliźniaczych (stan na listopad 2007) to Liczby te, znalezione w 2007 roku, posiadają 58711 cyfr w zapisie dziesiętnym[4].
Liczby pierwsze czworacze
Liczby czworacze
– liczby pierwsze,mające postać p, p+2, p+6, p+8, np. 5, 7, 11 i 13 lub 101, 103, 107 i 109, czyli dwie pary liczb bliźniaczych w najbliższym możliwym sąsiedztwie. Największe znane liczby czworacze to 4104082046 × 4799# + 5651, 4104082046 × 4799# + 5653, 4104082046 × 4799# + 5657 oraz 4104082046 × 4799# + 5659, gdzie # jest silnią.
Liczby pierwsze izolowane
Liczba pierwsza p jest izolowana, jeśli najbliższa jej liczba pierwsza różni się od p co najmniej o 4. Przykłady:23, 89, 157, 173.
Liczby pierwsze Mersenne'a
Liczbę
- M(n) := 2n – 1
nazywamy n-tą
liczbą Mersenne'a
(dla n=0, 1, ...). Tak otrzymana funkcja M jest homomorfizmem ze względu na największy wspólny dzielnik NWD:
- M(NWD(k, n)) = NWD(M(k), M(n)).
Liczby pierwsze Mersenna są to liczby pierwsze, będące jednocześnie liczbami Mersenne'a. Przykłady: 3, 7, 31, 127, 8191...
Warunkiem koniecznym, żeby liczba Mersenne'a M(n) była pierwsza jest pierwszość liczby n. Jednak nie dla każdej liczby pierwszej p, liczba M(p) jest pierwsza; na przykład
- 211 – 1 = 23·89
Dlatego bada się także dzielniki Mersenne'a, a mianowicie dzielniki liczb Mersenne'a M(p), dla p pierwszego, zwłaszcza dzielniki pierwsze.
W sierpniu
2008
roku największą znaną liczbą pierwszą była liczba Mersenne'a 243112609-1 – do jej zapisania w układzie dziesiętnym trzeba użyć 12978189 cyfr. Wygrano w ten sposób 100 tysięcy dolarów ufundowane przez Electronic Frontier Foundation dla odkrywcy liczby pierwszej o co najmniej 10 milionach cyfr[5].
Największymi znanymi liczbami pierwszymi były na ogół liczby Mersenne'a, gdyż istnieje dla nich efektywna metoda sprawdzenia, czy są pierwszymi, tak zwany
test Lucasa-Lehmera
.
Liczby złożone Mersenne'a
Liczby złożone Mersenne'a to liczby Mersenne'a M(p), które są złożone, gdy liczba p jest pierwsza (gdy p jest złożone, to M(p) jest zawsze złożone).
Zachodzi proste twierdzenie, które rzuca światło na ten problem:
- Stwierdzenie
Niech p oraz q := 2·p+1 będą liczbami pierwszymi, przy czym 2 jest resztą kwadratową mod q (t.zn. dla pewnej liczby całkowitej x). Wtedy q | M(p), więc liczba Mersenne'a M(p) jest wtedy złożona dla p > 3.
- Dowód
Przy założeniach twierdzenia, niech dla pewnej liczby całkowitej x. Wtedy na mocy
Małego Twierdzenia Fermata
:
czyli q | M(p). Ponieważ dla p > 3 zachodzi q := 2·p+1 < M(p), to q jest dzielnikiem właściwym, więc M(p) jest złożone dla p > 3 (przy pozostałych założeniach).
- Koniec dowodu.
Przykłady Wiadomo, że 2 jest resztą kwadratową nieparzystej liczby pierwszej q wtedy i tylko wtedy, gdy q² daje resztę -1 lub 1 z dzielenia przez 8. Ponadto chcemy, żeby p := (q-1)/2 było liczbą pierwszą. Zatem przykładów q, ilustrujących powyższe twierdzenie, należy szukać wyłącznie wśród q dających resztę -1 z dzielenia przez 8, czyli wśród liczb postaci: q = 8·n-1. Wtedy p = 4·n-1. Więc n nie powinno dawać reszty 1 z dzielenia przez 3, by uniknąć podzielności 3 | p, oraz nie powinno dawać reszty -1, by uniknąć 3 | q. Zatem należy ograniczyć się do n podzielnych przez 3, czyli do
- (p, q) := (12·k – 1, 24·k – 1)
Stąd najmniejszym przykładem, ilustrującym powyższe twierdzenie jest (p, q) := (11, 23). Otrzymujemy podzielność 23 | M(11). Następnym jest (p, q) := (23, 47), czyli podzielność 47 | M(23).
Liczby pierwsze Fermata
Są to liczby pierwsze postaci . Jak dotąd znanych jest jedynie pięć
liczb Fermata
, które są pierwsze: 3, 5, 17, 257 i 65537
a oto przykładowe
faktoryzacje
liczb Fermata
- F5 = 641 × 6700417
- F6 = 274177 × 67280421310721
Skoro liczby Fermata nie muszą być pierwsze, to bada się dzielniki Fermata, czyli dzielniki
liczb Fermata
, zwłaszcza dzielniki pierwsze.
Liczby pierwsze Sophie Germain
Liczbę pierwszą p nazywamy liczbą pierwszą
Sophie Germain
jeżeli liczba 2p + 1 również jest pierwsza. Oto kilka liczb tego rodzaju: 2, 3, 5, 11, 23, 29, 41, 53, 83... Liczby pierwsze Germain związane są ze szczególnymi przypadkami
wielkiego twierdzenia Fermata
.
Widzieliśmy też powyżej, że liczby pierwsze Germain występują w kontekście liczb złożonych Mersenne'a.
Liczby pomiędzy pierwsze
Liczby będące
średnią
kolejnych dwóch liczb pierwszych większych od 2 (
ang.
interprime numbers). Początkowe liczby pomiędzy pierwsze to: 4, 6, 9, 12, 15, 18, 21, 26, 30, 34, …
Liczby te są oczywiście
liczbami złożonymi
, ponieważ analizie poddajemy kolejne liczby pierwsze.
Liczby pseudopierwsze
Liczby złożone n, które spełniają warunek: n | 2n − 2. Istnieje nieskończenie wiele liczb pseudopierwszych parzystych, jak i nieparzystych. Co więcej, dla każdej liczby pierwszej p istnieje nieskończenie wiele liczb pseudopierwszych podzielnych przez p. Liczbami pseudopierwszymi dla danego
testu pierwszości
nazywamy liczby złożone, których ten test nie rozpoznaje (powyższy przykład to liczby pseudopierwsze dla
testu Fermata
przy a równym 2.
Liczby lustrzane
To pary liczb pierwszych, z których jedna powstaje przez zapisanie cyfr dziesiętnych drugiej w odwrotnej kolejności. Przykłady: 13 i 31, 17 i 71, 37 i 73, 79 i 97, 107 i 701,...
Liczby palindromiczne pierwsze
To liczby pierwsze, które nie zmieniają się, gdy ich cyfry dziesiętne zapiszemy w odwrotnej kolejności. Przykłady: 11, 101, 131, 191, 929.
Problemy
Zagadnienia dotyczące liczb pierwszych należą do
teorii liczb
. Istnieją w niej dotąd nie udowodnione hipotezy:
-
hipoteza Goldbacha
: czy każda liczba parzysta większa od 2 może być przedstawiona w postaci sumy dwóch liczb pierwszych?
- czy
ciąg Fibonacciego
zawiera nieskończenie wiele liczb pierwszych?
- czy liczb pierwszych Fermata jest nieskończenie wiele?
- czy liczb pierwszych bliźniaczych jest nieskończenie wiele?
- czy liczb
pierwszych Mersenne'a
jest nieskończenie wiele?
- czy liczb pierwszych Germain jest nieskończenie wiele?
- czy istnieje nieskończenie wiele liczb pierwszych postaci n² + 1?
- czy dla dowolnego n pomiędzy liczbami n² i (n + 1)² istnieje liczba pierwsza?
Największe znane liczby pierwsze
Największa odkryta dotąd liczba pierwsza to 46 (znana)
liczba pierwsza Mersenne'a
: 243112609−1 i liczy sobie 12978189 cyfr w zapisie dziesiętnym[5]. Została ona odkryta
23 sierpnia
2008
roku przez Edsona Smitha – uczestnika projektu
GIMPS
. Poprzednia największa liczba pierwsza, 44 liczba Mersenne'a, została odkryta we wrześniu 2006.
Electronic Frontier Foundation
ustanowiła nagrodę 100 tysięcy dolarów dla odkrywcy liczby pierwszej o więcej niż 10 milionach cyfr oraz nagrodę 150 tysięcy dolarów dla odkrywcy liczby pierwszej o więcej niż 100 milionach cyfr[6].
We wrześniu
2008
roku osiem największych znanych liczb pierwszych to liczby pierwsze Mersenne'a. Największą znaną liczbą pierwszą, która nie jest liczbą Mersenne'a jest:
która w zapisie dziesiętnym liczy 3 918 990 cyfr. Liczba ta jest dziewiątą największą znaną liczbą pierwszą i została odkryta
26 marca
2007
roku w ramach projektu Seventeen or Bust[5].
Największą liczbą pierwszą poznaną przed erą elektroniki jest 44-cyfrowa tzw.
liczba Ferriera
:
znaleziona za pomocą mechanicznego kalkulatora.
Odpowiedniki w innych strukturach algebraicznych
Najbliższym odpowiednikiem liczb pierwszych w
pierścieniach
są
elementy pierwsze
. Liczby pierwsze nie są jednak tym samym, co elementy pierwsze pierścienia liczb całkowitych – elementami pierwszymi są także liczby ujemne (-2, -3, -5, ...), a według niektórych źródeł także zero[7], które zostały z definicji wykluczone ze zbioru liczb pierwszych.
W pierścieniach bez jednoznaczności rozkładu pierwszość elementu nie jest równoważna jego nierozkładalności na czynniki (istnieją elementy nierozkładalne, które nie są pierwsze). Również pojęcie
ideału pierwszego
nawiązuje do tych intuicji.
Zastosowanie
Liczby pierwsze są stosowane w niektórych znanych
algorytmach
kryptograficznych
. Jednym z takich jest
RSA
. Rozwój tych
algorytmów
zapewnia rozwój projektów wyszukiwania ogromnych liczb pierwszych, takich jak
GIMPS
.
Przypisy
- ↑ Zero nie jest liczbą pierwszą, bo ma nieskończoną liczbę dzielników, a nie dokładnie dwa. Jeden nie jest liczbą pierwszą, bo ma tylko jeden dzielnik (siebie) a nie dokładnie dwa. Zero i jeden nie są liczbami złożonymi bo nie są większe od jeden.
- ↑ 2,0 2,1 2,2 Lew G. Sznirelman,Liczby Pierwsze, PWN, Warszawa 1954
- ↑ 3,0 3,1 3,2 William J. LeVeque © 1977, Fundamentals of Number Theory, Dover Publications 1996,
- ↑
The Largest Known Primes
- ↑ 5,0 5,1 5,2
Largest Known Primes history
(
ang.
)
- ↑
EFF Cooperative Computing Awards
- ↑ Na podstawie definicji w Fritz Reinhardt, Heinrich Soeder: Atlas matematyki. Prószyński i S-ka, s. 121. . . W podręczniku Algebry Białynickiego-Biruli zero jest jednak z definicji elementu pierwszego wykluczone
Bibliografia
Istnieje bardzo wiele książek o teorii liczb i liczbach pierwszych; między innymi:
-
Lew G. Sznirelman
, Liczby pierwsze, PWN, Warszawa 1954;
- William J. LeVeque © 1977, Fundamentals of Number Theory, Dover Publications 1996, ;
-
Jean-Pierre Serre
, A Course in Arithmetic, Springer-Verlag © 1973, , .
Zobacz też
Linki zewnętrzne