Liczba pierwsza
Liczba pierwsza to liczba naturalna określonego rodzaju. Każda liczba naturalna jest równa 1 razy siebie. Jeśli liczba jest równa jakiejkolwiek innej liczbie pomnożonej przez siebie, to liczba ta nazywana jest "liczbą złożoną". Najmniejszą liczbą złożoną jest 4, ponieważ 2 x 2 = 4. 1 nie jest liczbą złożoną. Każda inna liczba jest liczbą pierwszą. Liczby pierwsze to liczby inne niż 1, które nie są równe m x n (z wyjątkiem 1 x siebie). Najmniejszą liczbą pierwszą jest 2. Następne liczby pierwsze to 3, 5, 7, 11 i 13. Nie ma największej liczby pierwszej.
Sposób, w jaki występują liczby pierwsze, jest trudnym problemem dla matematyków. Gdy liczba jest większa, trudniej jest stwierdzić, czy jest ona liczbą pierwszą. Jedną z odpowiedzi na to pytanie jest twierdzenie o liczbach pierwszych. Jednym z nierozwiązanych problemów jest przypuszczenie Goldbacha.
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.
