Liczby pierwsze

Liczby pierwsze to liczby, które są podzielne tylko przez jeden i przez siebie. Właściwości liczb pierwszych są często wykorzystywane na przykład w kryptografii.

Definicje i przykłady

Liczba pierwsza to liczba naturalna, która jest podzielna przez jeden i samą siebie bez reszty, przy czym sama jedynka nie jest liczbą pierwszą. Najmniejszą liczbą pierwszą jest dwójka - jest ona podzielna bez reszty przez jeden i dwa. Jest to również jedyna liczba pierwsza, która jest parzysta. Wszystkie inne liczby pierwsze są nieparzyste, ponieważ każda inna liczba parzysta jest podzielna przez dwa oprócz jedynki i samej siebie.

Sekwencja kilku liczb pierwszych: 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, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271....

Liczby pierwsze są związane z podstawowym twierdzeniem arytmetyki, które mówi, że każdą liczbę całkowitą większą od 1 można rozłożyć na iloczyn liczb pierwszych.

Sprawdzanie, czy liczba jest pierwsza

Właściwości liczb pierwszych

• Istnieje nieskończenie wiele liczb pierwszych. Dowód można znaleźć w artykule o dowodzie przez zaprzeczenie.
• Dla każdej liczby całkowitej z>1 istnieje co najmniej jedna liczba pierwsza w przedziale (z, 2z). Przykład: dla z = 2 mamy przedział (2, 4). Jedyną liczbą całkowitą w tym przedziale jest trójka, która jest liczbą pierwszą. Dla z = 5 otrzymujemy przedział (5, 10), czyli liczby 6, 7, 8, 9. Liczba 7 jest liczbą pierwszą. Podobnie dla wyższych z.
• Liczba pierwsza Mersenne'a to liczba pierwsza, która jest o jeden mniejsza od pewnej całkowitej potęgi dwójki. Tak więc liczba pierwsza Mersenne'a M ma postać M = 2^z − 1, gdzie z jest dowolną liczbą naturalną. Przykładem może być liczba pierwsza 3, ponieważ zachodzi 2² − 1 = 3. Lub 7, ponieważ 2³ − 1 = 7.
• Największą znaną do tej pory liczbą pierwszą jest więc liczba pierwsza Mersenne'a, oznaczana jako M_43112609, gdzie indeks określa wykładnik z. Jest to więc liczba pierwsza 2^43112609−1. Została znaleziona 23 sierpnia 2008 roku i ma 12,978,189 cyfr.(Wikipedia)

Ciąg bez liczb pierwszych

Można znaleźć dowolnie długi skończony ciąg kolejnych liczb naturalnych, wśród których nie ma liczby pierwszej. Taki ciąg może mieć postać k!+2, k!+3, …, k!+k i zawierać k − 1 kolejnych liczb zespolonych (wykrzyknik oznacza czynnik).

Na przykład dla k = 6 otrzymujemy pięć kolejnych liczb zespolonych postaci: 720 + 2, 720 + 3, 720 + 4, 720 + 5, 720 + 6 Liczby te są kolejno podzielne przez dwa, trzy, cztery, pięć i sześć, ponieważ liczba 6! = 720 jest na pewno podzielna przez wszystkie te liczby, ponieważ powstała z ich iloczynu: 6! = 6 · 5 · 4 · 3 · 2 Jeśli liczba 720 jest podzielna przez trzy, to liczba 720 + 3 również musi być podzielna przez trzy. Podobnie dla pozostałych liczb.

Małe twierdzenie Fermata

Dla każdej liczby pierwszej p i dla każdej liczby całkowitej z takiej, że z nie jest wielokrotnością p, liczba z^p − z jest podzielna przez liczbę pierwszą p.

Przykład: rozważmy liczbę pierwszą p = 3 i liczbę całkowitą z = 4. Liczba cztery nie jest wielokrotnością liczby trzy, więc możemy kontynuować. Obliczmy wartość 4³ − 4. Jest ona równa 60. Ale w ten sposób, 60/4 = 15, liczba cztery dzieli sześćdziesiąt bez reszty, co odpowiada twierdzeniu Fermata. Inny przykład: p = 7, z = 10. Obliczamy wynik pośredni 10⁷ − 10 = 9999990 i dzielimy tę liczbę przez siedem: 9999990/7 = 1428570 Ponownie otrzymujemy wynik bez reszty.

Nierozwiązane pytania

Istnieje wiele dobrze znanych hipotez dotyczących liczb pierwszych, które nie zostały jeszcze (2011) udowodnione lub obalone. Dwie z najbardziej znanych to:

• Nieskończoność par liczb pierwszych: para liczb pierwszych to para liczb (z, z + 2), z których obie są liczbami pierwszymi. Na przykład (3, 5) lub (29, 31). Pytanie brzmi, czy takich par liczb pierwszych jest nieskończenie wiele. Zakłada się, że tak, ale brakuje dowodu.(Wikipedia)
• Hipoteza Riemanna: Wszystkie nietrywialne punkty zerowe funkcji zeta Riemanna mają część rzeczywistą równą $\frac12$.(Wikipedia) Twierdzenie to jest związane z rozkładem liczb pierwszych i jest jednym z tak zwanych problemów milenijnych, a za jego rozwiązanie przewidziana jest nagroda w wysokości miliona dolarów.