Login lub e-mail Hasło   

Liczby pierwsze - definicja liczby pierwszej

Odnośnik do oryginalnej publikacji: http://www.i-lo.tarnow.pl/edu/inf/alg/pr(...)ex.html
Liczba pierwsza jest liczbą naturalną posiadającą dokładnie dwa różne podzielniki - 1 oraz samą siebie. Wynika stąd, iż liczby 0 (nie jest liczbą natur...
Wyświetlenia: 28.888 Zamieszczono 03/11/2006
Liczba pierwsza jest liczbą naturalną posiadającą dokładnie dwa różne podzielniki - 1 oraz samą siebie.

Wynika stąd, iż liczby 0 (nie jest liczbą naturalną i nie dzieli się przez siebie) oraz 1 (ma tylko jeden podzielnik - samą siebie i nie jest on różny od 1) nie są liczbami pierwszymi. Oto kilka początkowych liczb pierwszych:

2 3 5 7 11 13 17 19 23 29 31 37 41 43 ...

Liczb pierwszych jest nieskończenie wiele.

Twierdzenie to udowodnił sławny matematyk starożytnej Grecji, Euklides. Założył on, iż zbiór liczb pierwszych jest skończony i zawiera np. n liczb pierwszych:

p1, p2, p3, ..., pn

Następnie utworzył ich iloczyn powiększony o 1 zgodnie ze wzorem:

E = (p1 p2 p3 ... pn) + 1

Otrzymana liczba E nie jest podzielna przez żadną liczbę pierwszą ze zbioru liczb pierwszych, ponieważ każde takie dzielenie daje resztę 1. Zatem pozostają tylko dwie możliwości:

  1. Liczba E jest nową liczbą pierwszą
  2. Liczba E jest podzielna przez liczbę pierwszą nie zawartą w zbiorze liczb pierwszych.

W obu tych przypadkach otrzymujemy nową liczbę pierwszą, co przeczy twierdzeniu, iż zbiór zawierał wszystkie liczby pierwsze. Skoro tak, to nie może on być zbiorem skończonym. Jest to tzw. dowód przez sprowadzenie do sprzeczności.

Przy wyszukiwaniu liczb pierwszych często zachodzi potrzeba sprawdzania podzielności dwóch liczb naturalnych. Do tego celu wykorzystywany jest operator reszty z dzielenia zwany operatorem modulo.

   
   
   

operator mod

10 mod 3 daje 1, ponieważ 3 mieści się w 10 trzy razy i pozostaje reszta 1

operator %

10 % 3 daje 1

 
       
Liczba n dzieli liczbę m, jeśli reszta z dzielenia m przez n wynosi 0.

Aby sprawdzić, czy dana liczba m jest liczbą pierwszą, należy dzielić ją przez kolejne liczby mniejsze od niej, a większe od 1. Jeśli przy każdym dzieleniu otrzymamy resztę różną od 0, m jest liczbą pierwszą. Jeśli natomiast choć jedno dzielenie daje resztę równą 0, m na pewno nie jest liczbą pierwszą. Tak wygląda pierwsze podejście do problemu wyznaczania liczb pierwszych - w dalszych rozdziałach postaramy się sprawę zbadać nieco dokładniej i dokonać daleko idących optymalizacji.

Słynni matematycy od dawna zaprzątali swoje umysły wzorem na liczby pierwsze. Dotychczas nie znaleziono jeszcze praktycznego wzoru na wszystkie liczby pierwsze. Istnieją tylko wzory pozwalające obliczać niektóre z nich (lub kilka z nich). Z usiłowań tych powstały sławne ciągi liczbowe.

Euklides urodził się około roku 365 p.n.e. Zmarł około roku 300 p.n.e. Był on matematykiem greckim pochodzącym z Aten, który przez większą część życia działał w sławnej Bibliotece Aleksandryjskiej. Był autorem pierwszych prac teoretycznych z matematyki, a jego dzieło Elementy stanowi syntezę ówczesnej wiedzy matematycznej.

Liczby Euklidesa powstają rekurencyjnie w następujący sposób:

e1 = 2,  e2 = 3 - stałe wartości początkowe
e3 = e1 e2 + 1 = 2 3 + 1 = 7
e4 = e1 e2 e3 + 1 = 43
e5 = e1 e2 e3 e4 + 1 = 1087
...
ei = e1 e2 ... ei-1 + 1

Tylko bardzo niewiele z liczb Euklidesa jest liczbami pierwszymi. Zwróć również uwagę na szybki wzrost ich wartości.

Pierre de Fermat urodził się w roku 1601, a zmarł w roku 1665. Był matematykiem francuskim, który dokonał bardzo wielu istotnych odkryć w dziedzinie rachunku różniczkowego i całkowego, teorii liczb, geometrii i rachunku prawdopodobieństwa.

W 1640 roku Pierre de Fermat napisał list do francuskiego mnicha, ojca Marina Mersenne'a, w którym zawarł przypuszczenie, iż wszystkie liczby otrzymane za pomocą wzoru:

Fi = 2 2i  + 1, gdzie i jest liczbą całkowitą nieujemną.
 

są pierwsze. Jednakże okazało się, iż liczby:

F0 = 3
F1 = 5
F2 = 17
F3 = 257
F4 = 65537

są co prawda liczbami pierwszymi, lecz liczba

F5 = 4294967297

nie jest pierwsza, ponieważ dzieli się przez 641, co udowodnił matematyk szwajcarski Leonard Euler. Liczby te rosną bardzo szybko, mimo to dzisiaj wiemy, iż dla kilkudziesięciu wartości i liczby Fi są złożone.

Marin Mersenne urodził się w roku 1588, a zmarł w roku 1648. Był francuskim filozofem, matematykiem i księdzem. Przyjaźnił się z Kartezjuszem. Interesował się problemem  wahadła oraz liczbami doskonałymi.

Ciąg ten zaproponował francuski mnich Marin Mersenne w 1644 roku podając następujący wzór::

Mn = 2n - 1

są pierwsze dla n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257, a dla żadnego innego n < 257 wzór nie daje w wyniku liczby pierwszej. Niestety, pomylił się, ponieważ dla n = 67 i 257 nie otrzymujemy liczby pierwszej, natomiast dla n = 61, 89 i 107 wzór daje w wyniku liczby pierwsze, których Mersenne nie wymienił.

Leonhard Euler urodził się w roku 1707, a zmarł w 1783. Był szwajcarskim matematykiem, fizykiem i astronomem, który wsławił się jako jeden z twórców matematyki współczesnej. Jego prace obejmowały niemal wszystkie znane w owym czasie dziedziny matematyki ze szczególnym uwzględnieniem analizy matematycznej.

W roku 1772 Leonhard Euler podał wzór wielomianu o postaci:

w(i) = i2 + i + 41

którego wartości dla i = 0, 1, 2, ..., 39 są liczbami pierwszymi.

 

Jeśli zainteresował cię temat liczb pierwszych, to zaglądnij do witryny: http://www.utm.edu/research/primes, gdzie zebrano o nich najświeższe informacje. Witryna jest w języku angielskim.

 

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Podobne artykuły


58
komentarze: 20 | wyświetlenia: 80676
61
komentarze: 41 | wyświetlenia: 9423
31
komentarze: 8 | wyświetlenia: 56521
31
komentarze: 7 | wyświetlenia: 86600
27
komentarze: 10 | wyświetlenia: 20336
23
komentarze: 5 | wyświetlenia: 19516
22
komentarze: 8 | wyświetlenia: 2112
14
komentarze: 8 | wyświetlenia: 100808
13
komentarze: 8 | wyświetlenia: 2029
13
komentarze: 55 | wyświetlenia: 21868
11
komentarze: 2 | wyświetlenia: 5273
9
komentarze: 3 | wyświetlenia: 15202
8
komentarze: 41 | wyświetlenia: 3830
16
komentarze: 5 | wyświetlenia: 9002
49
komentarze: 18 | wyświetlenia: 64968
 
Autor
Artykuł

Powiązane tematy






Brak wiadomości


Dodaj swoją opinię
W trosce o jakość komentarzy wymagamy od użytkowników, aby zalogowali się przed dodaniem komentarza. Jeżeli nie posiadasz jeszcze swojego konta, zarejestruj się. To tylko chwila, a uzyskasz dostęp do dodatkowych możliwości!
 

© 2005-2018 grupa EIOBA. Wrocław, Polska