Liczby pierwsze: definicja, przykłady, twierdzenia i zagadki
Poznaj liczby pierwsze — definicję, przykłady, kluczowe twierdzenia, testy i zagadki (w tym przypuszczenie Goldbacha). Przystępnie i z ciekawostkami.
Liczba pierwsza to liczba naturalna większa niż 1, która ma dokładnie dwa dzielniki: 1 i siebie samą. Innymi słowy, liczba pierwsza nie da się zapisać w postaci iloczynu dwóch liczb naturalnych większych od 1. Liczby, które można tak zapisać, nazywamy złożonymi (np. najmniejszą liczbą złożoną jest 4, bo 2 × 2 = 4). Liczba 1 nie jest ani pierwsza, ani złożona. Najmniejszą liczbą pierwszą jest 2 (to jedyna parzysta liczba pierwsza); kolejne to 3, 5, 7, 11, 13, 17, 19 itd. Nie istnieje największa liczba pierwsza — zbiór liczb pierwszych jest nieskończony.
Własności i przykłady
- Każda liczba pierwsza p ma dokładnie dwa dzielniki: 1 i p.
- Z wyjątkiem 2 wszystkie liczby pierwsze są nieparzyste (bo parzyste liczby większe niż 2 dzielą się przez 2).
- Fundamentalne twierdzenie arytmetyki: każda liczba naturalna większa od 1 da się jednoznacznie (z dokładnością do kolejności czynników) rozłożyć na iloczyn liczb pierwszych.
- Są specjalne rodzaje liczb pierwszych: bliźniacze (np. 11 i 13), Mersenne'a (postaci 2^p − 1 dla pewnych p), Fermata, bezpieczne i inne.
Dowód nieskończoności liczb pierwszych
Klasyczny dowód Euklidesa jest prosty i elegancki: przyjmijmy, że istnieje skończony zbiór liczb pierwszych p1, p2, ..., pn. Rozważ liczbę P = p1·p2·...·pn + 1. Liczba P nie dzieli się przez żadną z pi (bo dzielenie daje resztę 1), więc albo P jest pierwsza, albo ma dzielnik pierwszy spoza zbioru {p1,...,pn}. W obu przypadkach otrzymujemy nową liczbę pierwszą, sprzeczną z założeniem skończoności.
Rozkład i twierdzenia
Sposób, w jaki rozmieszczone są liczby pierwsze wśród liczb naturalnych, jest przedmiotem głębokich badań. Jednym z najważniejszych rezultatów jest twierdzenie o liczbach pierwszych, które opisuje asymptotyczny rozkład liczb pierwszych i mówi w przybliżeniu, ile liczb pierwszych znajduje się poniżej danej wartości (liczba pierwsza około n ma gęstość odwrotnie proporcjonalną do logarytmu n). Istnieje też wiele nierozwiązanych problemów — jednym z najsłynniejszych jest przypuszczenie Goldbacha (każda liczba parzysta większa niż 2 jest sumą dwóch liczb pierwszych).
Jak sprawdzić, czy liczba jest pierwsza
- Najprostsza metoda: dzielenie próbne — sprawdzamy podzielność przez wszystkie liczby pierwsze mniejsze lub równe √n. Jeśli żadna nie dzieli n, to n jest pierwsza.
- Optymalizacje: pominięcie parzystych dzielników (po sprawdzeniu 2), sprawdzanie tylko liczb postaci 6k ± 1, użycie sita Eratostenesa do wyznaczenia wszystkich liczb pierwszych do pewnego progu.
- Metody probabilistyczne: testy Fermata, Miller–Rabin — szybkie, dają dużą pewność, ale mogą dać wynik fałszywie pozytywny dla rzadkich liczb zwanych pseudopierwszymi.
- Metody deterministyczne dla dużych liczb: test AKS daje deterministyczny algorytm wielomianowy, ale jest praktycznie wolniejszy od dobrze zoptymalizowanych testów probabilistycznych dla zastosowań praktycznych.
Sito Eratostenesa — prosty sposób na listę pierwszych
Sito Eratostenesa to skuteczna metoda wyznaczania wszystkich liczb pierwszych mniejszych od pewnej granicy N. Polega na kolejnych eliminacjach wielokrotności liczb pierwszych: zaczynając od 2, skreślamy wszystkie jego wielokrotności, potem przechodzimy do następnej nieskreślonej liczby (3) i skreślamy jej wielokrotności, i tak dalej do √N. Złożoność obliczeniowa można zoptymalizować, a metoda jest bardzo użyteczna w praktyce.
Zastosowania liczb pierwszych
- Teoria kodowania i kryptografia — np. system RSA opiera się na trudności rozkładu dużych liczb złożonych na czynniki pierwsze.
- Generator liczb losowych, protokoły zabezpieczeń, testy integralności danych.
- Badania matematyczne: teoria liczb, badania nad rozkładem, konjektury (np. Goldbacha, bliźniaczych pierwszych).
Zagadki i przykłady do rozwiązania
- Znajdź wszystkie liczby pierwsze mniejsze niż 100 (można użyć sita Eratostenesa).
- Sprawdź, czy liczba 1 000 003 jest pierwsza (spróbuj dzielenia próbnego do √(1 000 003) lub testu Miller–Rabin).
- Zagadka: udowodnij, że wśród kolejnych n! + 2, n! + 3, ..., n! + n każdy składnik jest złożony — co to pokazuje o rozmieszczeniu liczb złożonych?
Sposób, w jaki występują liczby pierwsze, pozostaje wciąż pełen wyzwań i niespodzianek dla matematyków. W miarę jak rozmiary badanych liczb rosną, wykrywanie pierwszości staje się trudniejsze, ale jednocześnie rozwijane są coraz skuteczniejsze algorytmy i techniki badawcze. Wspomniane powyżej twierdzenie o liczbach pierwszych i przypuszczenie Goldbacha to tylko dwa przykłady zagadnień, które łączą teorię z praktycznymi zastosowaniami.
Oto inny sposób myślenia o liczbach pierwszych. Liczba 12 nie jest pierwsza, ponieważ można z niej zrobić prostokąt o bokach długości 4 i 3. Ten prostokąt ma pole 12, ponieważ wszystkie 12 bloków są używane. Nie da się tego zrobić z 11. Bez względu na to, jak ułożymy prostokąt, zawsze pozostaną klocki, z wyjątkiem prostokąta o bokach długości 11 i 1. 11 musi więc być liczbą pierwszą.
Jak znaleźć małe liczby pierwsze
Istnieje prosta metoda na znalezienie listy liczb pierwszych. Stworzył ją Eratostenes. Ma nazwę Sieve Eratostenesa. Wyłapuje ona liczby, które nie są pierwsze (jak sito) i przepuszcza liczby pierwsze.
Metoda ta działa na podstawie listy liczb oraz specjalnej liczby zwanej b, która zmienia się w trakcie metody. Gdy przechodzisz przez metodę, zakreślasz niektóre liczby na liście i przekreślasz inne. Każda zakreślona liczba jest pierwsza, a każda przekreślona liczba jest złożona. Na początku, wszystkie liczby są zwykłe: nie zakreślone i nie przekreślone.
Metoda jest zawsze taka sama:
- Na kartce papieru wypisz wszystkie liczby całkowite od 2 do liczby, która jest testowana. Nie zapisuj liczby 1. Przejdź do następnego kroku.
- Zacznij od b równego 2. Przejdź do następnego kroku.
- Zakreśl literę b na liście. Przejdź do następnego kroku.
- Zaczynając od b, policz do góry o b więcej na liście i przekreśl tę liczbę. Powtarzaj odliczanie kolejnych liczb o b i skreślanie liczb aż do końca listy. Przejdź do następnego kroku.
- (Na przykład: Gdy b jest równe 2, zakreślisz 2 i przekreślisz 4, 6, 8, itd. Gdy b jest równe 3, zakreślisz kółkiem 3 i przekreślisz 6, 9, 12, itd. 6 i 12 zostały już przekreślone. Przekreśl je ponownie.)
- Zwiększ b o 1. Przejdź do następnego kroku.
- Jeśli b zostało przekreślone, wróć do poprzedniego kroku. Jeśli b jest liczbą na liście, która nie została przekreślona, przejdź do trzeciego kroku. Jeśli b nie znajduje się na liście, przejdź do ostatniego kroku.
- (To jest ostatni krok.) Skończyłeś. Wszystkie liczby pierwsze są zakreślone, a wszystkie liczby złożone są przekreślone.
Jako przykład, można zrobić tę metodę na liście liczb od 2 do 10. Na końcu, numery 2, 3, 5 i 7 będą kończyć się zakreślone. Są one liczbami pierwszymi. 4, 6, 8, 9 i 10 zostaną przekreślone. Są to liczby złożone.
Ta metoda lub algorytm trwa zbyt długo, aby znaleźć bardzo duże liczby pierwsze. Ale jest mniej skomplikowana niż metody używane dla bardzo dużych liczb pierwszych, takie jak test prymitywności Fermata (test sprawdzający, czy liczba jest prymitywna czy nie) lub test prymitywności Millera-Rabina.
Do czego używane są liczby pierwsze
Liczby pierwsze są bardzo ważne w matematyce i informatyce. Niektóre z ich zastosowań w świecie rzeczywistym są podane poniżej. Bardzo długie liczby są trudne do rozwiązania. Trudno jest znaleźć ich czynniki pierwsze, więc większość czasu, liczby, które są prawdopodobnie pierwszymi są używane do szyfrowania i tajnych kodów.
- Większość ludzi posiada kartę bankową, za pomocą której może pobierać pieniądze z konta, korzystając z bankomatu. Karta ta jest chroniona przez tajny kod dostępu. Ponieważ kod ten musi być utrzymywany w tajemnicy, nie może być przechowywany w postaci czystego tekstu na karcie. Szyfrowanie jest używane do przechowywania kodu w sposób tajny. W szyfrowaniu wykorzystuje się mnożenie, dzielenie i znajdowanie reszt z dużych liczb pierwszych. W praktyce często stosowany jest algorytm o nazwie RSA. Wykorzystuje on chińskie twierdzenie o resztach.
- Jeśli ktoś ma podpis cyfrowy dla swojej wiadomości e-mail, używane jest szyfrowanie. Daje to pewność, że nikt nie może podrobić wiadomości od niego. Przed podpisaniem, tworzona jest wartość hash wiadomości. Jest ona następnie łączona z podpisem cyfrowym w celu uzyskania podpisanej wiadomości. Stosowane metody są mniej więcej takie same jak w pierwszym przypadku powyżej.
- Znalezienie największej znanej do tej pory liczby pierwszej stało się swego rodzaju sportem. Sprawdzenie, czy dana liczba jest pierwsza, może być trudne, jeśli liczba jest duża. Największe znane w danym momencie liczby pierwsze są zazwyczaj liczbami Mersenne'a, ponieważ najszybszym znanym testem na pierwotność jest test Lucasa-Lehmera, który opiera się na specjalnej formie liczb Mersenne'a. Grupa, która poszukuje liczb pierwszych Mersenne'a znajduje się tutaj[1].
Pytania i odpowiedzi
P: Co to jest liczba pierwsza?
A: Liczba pierwsza to liczba naturalna, która nie może być podzielona przez żadną inną liczbę naturalną z wyjątkiem 1 i samej siebie.
P: Jaka jest najmniejsza liczba zespolona?
O: Najmniejszą liczbą złożoną jest 4, ponieważ 2 x 2 = 4.
P: Jakie są następne liczby pierwsze po 2?
O: Następne liczby pierwsze po 2 to 3, 5, 7, 11 i 13.
P: Czy istnieje największa liczba pierwsza?
O: Nie, nie ma największej liczby pierwszej. Zbiór liczb pierwszych jest nieskończony.
P: Co mówi podstawowe twierdzenie arytmetyki?
O: Podstawowe twierdzenie arytmetyki mówi, że każdą liczbę całkowitą dodatnią można zapisać jako iloczyn liczb pierwszych w niepowtarzalny sposób.
P: Co to jest domysł Goldbacha?
A: Domysł Goldbacha to nierozwiązany problem w matematyce, który mówi, że każda parzysta liczba całkowita większa od dwóch może być wyrażona jako suma dwóch liczb pierwszych.
P: Kto zapisał dowód, że nie ma największej liczby pierwszej?
O: Euklides zapisał dowód, że nie ma największej liczby pierwszej.
Przeszukaj encyklopedię