Liczby pierwsze - definicja liczby pierwszej

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:

p₁, p₂, p₃, ..., p_n

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

E = (p₁ p₂ p₃ ... p_n) + 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:

Liczba E jest nową liczbą pierwszą
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:

e₁ = 2, e₂ = 3 - stałe wartości początkowe
e₃ = e₁ e₂ + 1 = 2 3 + 1 = 7
e₄ = e₁ e₂ e₃ + 1 = 43
e₅ = e₁ e₂ e₃ e₄ + 1 = 1087
...
e_i = e₁ e₂ ... e_i-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:

F_i = 2 2ⁱ + 1, gdzie i jest liczbą całkowitą nieujemną_.

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

F₀ = 3
F₁ = 5
F₂ = 17
F₃ = 257
F₄ = 65537

są co prawda liczbami pierwszymi, lecz liczba

F₅ = 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 F_i 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::

M_n = 2ⁿ - 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) = i² + 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.

Źródło: mgr Jerzy Wałaszek

liczby technologia programowanie

F_i = 2	2ⁱ	+ 1, gdzie i jest liczbą całkowitą nieujemną_.

Liczby pierwsze - definicja liczby pierwszej

operator mod

operator %