Euklides
EUKLIDES

LICZBY PIERWSZE


W tym rozdziale:

Definicja liczby pierwszej
Rozkład czynników pierwszych liczby naturalnej
Liczby Euklidesa
Liczby Fermata
Liczby Mersenne'a
Liczby Eulera

WSTĘP

Liczby pierwsze znane już były starożytnym uczonym Greckim. Ich znaczenie dla matematyki nie uległo zmianie do dnia dzisiejszego. Są one stosowane intensywnie w teorii liczb, w szyfrowaniu wiadomości, w rozbiorze na czynniki pierwsze itd. Dlatego umiejętność znajdowania liczb pierwszych jest jedną z podstawowych umiejętności, które powinien posiąść adept sztuk informatycznych. W naszym opracowaniu podamy proste sposoby tworzenia liczb pierwszych oraz przykłady ich zastosowania.

Definicja liczby pierwszej

Zaczniemy najpierw od samej definicji liczby pierwszej, która brzmi następująco

Liczba pierwsza jest liczbą naturalną, która dzieli się całkowitą liczbę razy tylko przez jeden oraz przez siebie samą. Liczby 0 i 1 nie są liczbami pierwszymi.

Definicja powyższa daje nam istotną wskazówkę, jak poszukiwać liczb pierwszych lub sprawdzać, czy dana liczba jest pierwsza. Dużą rolę odgrywają reszty z dzielenia całkowitoliczbowego. W arytmetyce określono działanie o nazwie modulo. Wynik stanowi reszta z dzielenia:

20 modulo 3 = 2, ponieważ 3 mieści się 6 razy w 20, co daje 18 i resztę 2.

Sprawdzenie podzielności dwóch liczb sprowadza się do zbadania reszty z dzielenia pierwszej liczby przez drugą. Jeśli reszta jest różna od zera, to dane dwie liczby nie dzielą się całkowitą liczbę razy. W przypadku reszty równej zero liczba druga dzieli pierwszą. Ze sposobu tego szeroko korzysta się w programach komputerowych.

a modulo b = 0 Þ  a jest podzielne przez b
a modulo b <> 0
Þ  a nie jest podzielne przez b

Liczba n jest pierwsza, jeśli dla każdej liczby pierwszej p, p < n, zachodzi n modulo p <> 0.

Powyżej przedstawiamy definicję liczby pierwszej wykorzystującą działanie modulo. Jest ona oczywiście równoważna definicji podanej wcześniej. Przyjmijmy do wiadomości fakt, iż jak dotąd nie znaleziony został żaden ogólny wzór pozwalający obliczać poszczególne liczby pierwsze, a jest ich nieskończenie wiele. Wykazał to grecki uczony Euklides w dziele "Elementy", podając dowód dla następującego rozumowania:

Załóżmy, że liczb pierwszych jest skończona ilość. Oznaczmy je kolejnymi indeksami:

p1, p2, p3, ..., pi-1, pi

wtedy liczba E = p1 p2 p3 ... pi-1 pi + 1 jest albo sama liczbą pierwszą, albo podzielna jest przez liczbę pierwszą różną od p1, p2, p3, ..., pi-1, pi. W obu przypadkach dostajemy kolejną liczbę pierwszą, co przeczy założeniu, iż liczb tych jest skończona ilość.

Rozkład czynników pierwszych liczby naturalnej

Każdą liczbę naturalną większą od 1 da się przedstawić w postaci iloczynu liczb pierwszych, które nazywamy czynnikami pierwszymi tej liczby naturalnej:

n = p1 x p2 x ... pm
gdzie n - liczba naturalna większa od 1, p1...pm liczby pierwsze mniejsze lub równe n

Rozważmy możliwe rozkłady czynników pierwszych dla dowolnej liczby naturalnej (większej od 1!). Mogą zachodzić cztery możliwości:

  1. Jeden z czynników jest równy pierwiastkowi z danej liczby. Wtedy liczba naturalna n posiada dokładnie dwa czynniki pierwsze:

n = p x p, gdzie p = √n

np. 9 = 3 x 3

  1. Wszystkie czynniki pierwsze liczby n są mniejsze od wartości jej pierwiastka:

n = p1 x p2 x ... x pm, gdzie p1 ≤ p2 ≤ ... ≤ pm < √n

np. 12 = 2 x 2 x 3

  1. Dokładnie jeden z czynników jest większy od pierwiastka z n (takich czynników nie może więcej niż jeden, gdyż ich iloczyn byłby wtedy większy od liczby n!). Jeśli czynnik ten jest mniejszy od liczby n, to istnieją dalsze czynniki pierwsze o wartościach mniejszych od pierwiastka z liczby n:

n = p1 x p2 x ... x pm-1 x pm, gdzie p1 ≤ p2 ≤ pm-1 < √n < pm < n

np. 20 = 2 x 2 x 5

  1. Liczba nie posiada czynników pierwszych mniejszych lub równych jej pierwiastkowi. W takim przypadku jest ona sama liczbą pierwszą.

Z analizy rozkładu czynników pierwszych wynika dla nas bardzo ważny wniosek. Jeśli chcemy sprawdzić, czy dana liczba naturalna jest liczbą pierwszą, to wystarczy przetestować jej podzielność przez liczby pierwsze mniejsze lub równe jej pierwiastkowi (jeśli pierwiastek jest całkowity, to nawet nie musimy sprawdzać dalej, gdyż liczba na pewno nie jest wtedy liczbą pierwszą). Dzięki takiemu podejściu znakomicie zmniejszamy ilość sprawdzeń podzielności. Np. dla liczb do 100 wystarczy sprawdzić podzielność przez 2, 3, 5 lub 7.

Sławne ciągi liczbowe

Słynni matematycy od dawna zaprzątali swoje umysły wzorem na liczby pierwsze. Dotychczas nie znaleziono jeszcze 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.

Liczby Euklidesa

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

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

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

Liczby Fermata

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
 

są pierwsze. Przeliczył on cztery początkowe liczby dla i = 1, 2, 3 i 4, lecz zabrakło mu już cierpliwości dla kolejnych liczb. Trudno się jest dziwić panu Fermatowi, piąta liczba ma już 10 cyfr i nie jest pierwsza.

Liczby Mersenne'a

Ciąg ten zaproponował francuski mnich Marin Mersenne w 1644 roku. Napisał on, iż liczby o postaci:

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 równego 67 i 257 nie otrzymujemy liczby pierwszej, natomiast dla n równego 61, 89 i 107 wzór daje w wyniku liczby pierwsze, których Mersenne nie wymienił.

Liczby Eulera

W roku 1772 Leonard 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 na stronę: http://www.utm.edu/research/primes, gdzie zebrano najświeższe wiadomości o nich. Strona w języku angielskim.


Tworzenie liczb pierwszych | Podsumowanie