liczbypierwsze.com

Baza wiedzy

Wprowadzenie

Wiele liczb naturalnych daje się rozłożyć na czynniki mniejsze np. 10=5*2 lub 111=3*37. Jednak istnieją liczby, które nie mogą być rozłożone w taki sposób. Takie liczby nazywamy liczbami pierwszymi.

Liczba pierwsza to taka liczba całkowita p większa od jedności, której jedynymi dziennikami są 1 oraz p. Każdą liczbę naturalną większą od jedności, która nie jest liczbą pierwszą, nazywamy liczbą złożoną.

Pierwsze 34 liczby pierwsze to : 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, 101, 103, 107, 109, 113, 127, 131, 137, 139

 
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 70
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 66 97 98 99 100
wykaz liczb pierwszych od 1 do 100. Liczby pierwsze są zaznacxone na czerwono.
 

Liczb pierwszych jest nieskończenie wiele. Niech π(n) będzie określało ilość liczb pierwszych nie większych od n. Dla dużych wartości liczby n mamy wzór:

Oto kilka przykładów : liczb pierwszych mniejszych od 1000 jest 168. Wśród wszystkich liczb 100-yfrowych w przybliżeniu jedna na każde 300 jest liczbą pierwszą.

 

Sito Eratostenesa

Najpopularniejszym algorytmem wyznaczania liczb pierwszych jest Sito Eratostenesa. Oto algorytm :
 

Gęstość liczb pierwszych

Teraz wprowadzamy nowe pojęcie gęstości liczb pierwszych. Niech An oznacza ilość liczb pierwszych wśród liczb naturalnych 1,2,3,...,n. Zatem :

Gęstość liczb pierwszych wśród n pierwszych liczb całkowitych jest dana przez stosunek : An / n Poniżej przedstawiam tabelę zawierającą procent liczb pierwszych w danym przedziale [a,b] :

a b procent
2 2 100%
2 4 667%
2 8 57,16%
2 16 40%
2 32 35,48%
2 64 28,57%
2 128 24,41%
2 256 21,18%
2 512 18,98%
2 1024 16,81%
2 2048 15,1%
2 4096 13,77%
2 8192 12,55%
2 8192 12,55%
2 16384 11,60%
2 32768 10,72%
2 131072 9,35%
2 262144 8,77%
2 524288 8,28%
2 1048576 7,82%
Gęstość liczb pierwszych w danym przedziale
 
Niech π(n) będzie określało ilość liczb pierwszych nie większych od n. Jak już wspomniałem - dla dużych wartości liczby n mamy wzór:
 

twierdzenie o liczbach pierwszych mówi nam, że :
 
dąży do 1 przy wzroście liczby n.
 

Rodzaje liczb pierwszych


Liczby Mersenne'a Wtedy Mq jest liczbą Mersenne'a. Sprośród wszystkich wygenerowanych do tej pory liczb tego typu zaledwie 48 to liczby pierwsze.
 
Liczby pierwsze bliźniacze.
Liczby bliźniacze to dwie liczby pierwsze róźniące się o 2.Na przykład
 
Liczby pierwsze czworacze
Liczby czworacze to takie liczby: p , p+2, p+6, p+8, że każda z nich jest liczbą pierwszą.Na przykład:
 
Liczby pierwsze izolowane
Liczba pierwsza p jest izolowana, jeśli najbliższa liczba pierwsza różni się od niej co najmniej o 4.
 
Liczby Sophie Germain
 
Liczby pierwsze lustrzane
To pary liczb pierwszych, z których jedna powstaje przez zapisanie cyfr dziesiętnych drugiej w odwrotnej kolejności. Przykłady:
 
Liczby pierwsze palindromiczne
To liczby pierwsze, które nie zmieniają się, gdy ich cyfry dziesiętne zapiszemy w odwrotnej kolejności. Przykłady:
 

Wzory na liczby pierwsze

Próbowano znaleźć proste wzory arytmetyczne, które dawałyby tylko liczby pierwsze, chociaż niekoniecznie wszystkie liczby pierwsze. Fermat wysunął słynne przypuszczenie, że wszystkie liczby postaci : F(n) = 22n + 1 są liczbami pierwszymi. Rzeczywiści dla n=1,2,3,4 otrzymujemy : Wszystkie powyższe liczby są pierwsze. Ale w roku 1723 Euler odkrył, że F(5)=641*6700417 nie jest liczbą pierwszą.
 
Innym ciekawym wyrażeniem, które daje wiele liczb pierwszych jest Dla n=1,2,3,...,40 wyrażenie f(n) jest liczbą pierwszą. Natomiast dla n=41 mamy f(n)=412 i jest to liczba złożona.
 
Wyrażenie daje liczby pierwsze przy wszelkich wartościach n aż do 79. Zawodzi jednak dla n=80
 

Testy pierwszości

Aby sprawdzić, czy liczba naturalna n jest liczbą pierwszą, należy dzielić ją kolejno przez wszystkie liczby większe od 1 i mniejsze równe od floor(n/2). Jeśli przy każdym dzieleniu reszta z dzielenia jest różna od zera, to liczba jest liczbą pierwszą. Natomiast jeżeli choć jedno dzielenie daje resztę równą zero, to sprawdzana liczba naturalna jest liczbą złożoną.
 
Oto przykład funkcji sprawdzającej czy dana liczba n jest liczbą pierwszą. Funkcja została napisana w języku PHP:
 
function is_prime($n)
{
$wynik=0;
$i=2;
$g=floor($n/2);
while (($wynik==0) & ($i<=$g))
{
if ($n%$i==0) ++$i;
}
if ($wynik==0) return(0);
else return(1);
}
 
Jeżeli funkcja zwróci wartość 0 to liczba n jest liczbą pierwszą.
 

Spirala Ulama

W matematyce spirala Ulama lub spirala liczb pierwszych to graficzna metoda pokazywania pewnych niewyjaśnionych do dziś różnic w rozkładzie liczb pierwszych, zaproponowana przez polskiego matematyka Stanisława Ulama w 1963 roku. Na kwadratowej tablicy zaczynając od 1 wśrodku spiralnie wypisuje się kolejne liczby naturalne. Na niektórych przekątnych liczby pierwszej częściej grupują się niż na innych. Fakt ten nie został do tej pory wyjaśniony.
 

Liczby od 1 do 50 w układzie spirali Ulama
 

Liczby pierwsze w Spirali Ulama w układzie 200x200
 

Liczby pierwsze od 1 do 50 w tym samym układzie
 

Hipotezy

Czego nie wiadomo o liczbach pierwszych:
 

Ciekawostki

 

Największe liczby pierwsze

Największa odkryta dotąd liczba pierwsza to 274207281−1, która liczy sobie 22338618 cyfr w zapisie dziesiętnym. Została ona odkryta przez Curtisa Coopera 7 stycznia 2016 roku. Oto lista innych wielkich liczb pierwszych:
Liczba pierwsza Liczba cyfr Rok odkrycia
274207281-1 22338618 2016
257885161-1 17425170 2013
243112609-1 12978179 2008
Największe liczby pierwsze
 
Największą liczbą pierwszą sprzed ery komputerów jest liczba, która nosi nazwę odkrywcy - liczba Ferriera i wynosi:

20 988 936 657 440 586 486 151 264 256 610 222 593 863 921


Jest to 44-cyfrowa liczba znaleziona za pomocą mechanicznego kalkulatora w 1951r.
 

Kryptografia

Duże liczby pierwsze są często wykorzystywane w kryptografii ze względu na swe specyficzne właściwości. Dla przykładu opiszę kryptosystem RSA. Wykorzystujemy tutaj dwie pary kluczy. klucz publiczny i klucz prywatny.
 
Algorytm RSA:
 

Algorytmy probabilistyczne

Algorytmy probabilistyczne z bardzo dużym prawdopodobieństwem sprawdzają czy dana liczba jest liczbą pierwszą. Ale niestety istnieje niewielkie prawdopodobieństwo pomyłki.
 
Algorytm:

  1. Wprowadź liczbę n

  2. Wybierz losowo liczbę k z przedziału [1,n-1]

  3. Sprawdź czy liczba k świadczy o złożoności liczby n

    1. Jeżeli tak to liczba n nie jest liczbą pierwszą

    2. Jeżeli nie to sprawdź czy sprawdzono już 200 różnych liczb k

      1. Jeżeli nie to wróć do punktu 2

      2. Jeżeli tak to n jest liczbą pierwszą

W powyższym algorytmie prawdopodobieństwo pomyłki jest mniejsze niż 1/200.
 

Funkcja Eulera

Dla każdego n>=1 niech φ(n) będzie liczbą takich liczb całkowitych z przedziału 1<=a<=n, że NWD(a,n)=1. Wtedy funkcję φ nazywamy funkcją Eulera.
 
Małe twierdzenie Fermata
Jeżeli p jest liczbą pierwszą, nie będącą dzielnikiem liczby całkowitej a to :
 
aφ(p) ≡ 1 (mod p)
 
Oto przykład algorytmu wyliczającego funkcję Eulera w języku PHP. Użyłem funkcji pomocniczej nwd, która oblicza największy wspólny dzielnik dla dwóch liczb naturalnych większych od 0.
 
function nwd($a,$b)
{
while($a*$b!=0)
{
if ($a>$b)
{
$a=$a%$b;
}
else
{
$b=$b%$a;
}
}$wynik=$a+$b;
return($wynik);
}


function euler($n)
{
$wynik=0;
for ($i=1;$i<$n;++$i)
{
$sprawdz=nwd($i,$n);
if ($sprawdz==1) ++$wynik;
}
return($wynik);
}
 
W poniższej tabeli podałem wartości funkcji Eulera dla kolenych potęg liczby 10.
n φ(n)
10 4
100 40
1000 400
10000 4000
wartości funkcji Eulera dla kolenych potęg liczby 10
 

Książki o liczbach pierwszych

 

Prawa autorskie

Zawartość powyższej strony internetowej ( https://liczbypierwsze.com ) jest udostępniona na otwartej licencji Creative Commons. Masz swobodę do wykorzystania materiałów znajdujących się na tej stronie w dowolnym celu - możesz wydrukować je studentom lub wyświetlić na szkoleniu.
 
W szczególności:
 
Więcej informacji na ten temat znajdziesz na stronie internetowej:
 
znajdziesz tutaj
 

Kontakt

 
Więcej informacji znajdziesz na stronie : https://jpn44.com
 
Jesteś Gościem numer 71