W artykule omówiono pojęcia liczb pierwszych i liczb złożonych. Podano definicje takich liczb wraz z przykładami. Podajemy dowód, że liczba liczb pierwszych jest nieograniczona i dokonujemy wpisu w tablicy liczb pierwszych metodą Eratostenesa. Zostaną podane dowody, czy liczba jest pierwsza, czy złożona.
Yandex.RTB R-A-339285-1
Liczby pierwsze i złożone - definicje i przykłady
Liczby pierwsze i złożone są zaliczane do dodatnich liczb całkowitych. Muszą być większe niż jeden. Dzielniki dzielą się również na proste i złożone. Aby zrozumieć pojęcie liczb złożonych, należy najpierw przestudiować pojęcia dzielników i wielokrotności.
Definicja 1
Liczby pierwsze to liczby całkowite, które są większe od jeden i mają dwa dodatnie dzielniki, czyli siebie i 1.
Definicja 2
Liczby złożone to liczby całkowite większe od jeden i mające co najmniej trzy dodatnie dzielniki.
Jeden nie jest ani liczbą pierwszą, ani złożoną. Ma tylko jeden dodatni dzielnik, więc różni się od wszystkich innych liczb dodatnich. Wszystkie dodatnie liczby całkowite nazywane są naturalnymi, to znaczy używanymi do liczenia.
Definicja 3
liczby pierwsze są liczbami naturalnymi, które mają tylko dwa dodatnie dzielniki.
Definicja 4
Liczba złożona jest liczbą naturalną, która ma więcej niż dwa dodatnie dzielniki.
Każda liczba większa niż 1 jest liczbą pierwszą lub złożoną. Z własności podzielności mamy, że 1 i liczba a zawsze będzie dzielnikami dowolnej liczby a, to znaczy będzie podzielna przez siebie i przez 1. Podajemy definicję liczb całkowitych.
Definicja 5
Liczby naturalne, które nie są pierwszymi, nazywamy liczbami złożonymi.
Liczby pierwsze: 2, 3, 11, 17, 131, 523. Dzielą się tylko przez siebie i przez 1. Liczby złożone: 6, 63, 121, 6697. Oznacza to, że liczbę 6 można rozłożyć na 2 i 3, a 63 na 1, 3, 7, 9, 21, 63 i 121 na 11, 11, to znaczy jej dzielnikami będą 1, 11, 121. Liczba 6697 rozłoży się na 37 i 181. Zauważ, że koncepcje liczb pierwszych i liczb względnie pierwszych to różne koncepcje.
Aby ułatwić korzystanie z liczb pierwszych, musisz użyć tabeli:
Tabela dla wszystkich istniejących liczb naturalnych jest nierealistyczna, ponieważ istnieje ich nieskończona liczba. Kiedy liczby osiągną rozmiary 10000 lub 1000000000, warto pomyśleć o zastosowaniu sita Eratostenesa.
Rozważ twierdzenie wyjaśniające ostatnie stwierdzenie.
Twierdzenie 1
Najmniejszy dodatni dzielnik liczby naturalnej większej niż 1 inny niż 1 jest liczbą pierwszą.
Dowód 1
Załóżmy, że a jest liczbą naturalną większą od 1, b jest najmniejszym dzielnikiem liczby a. Musimy udowodnić, że b jest liczbą pierwszą metodą sprzeczności.
Powiedzmy, że b jest liczbą złożoną. Stąd mamy, że istnieje dzielnik dla b , który jest różny zarówno od 1, jak i od b . Taki dzielnik oznaczamy jako b 1 . Konieczne jest, aby warunek 1< b 1 < b została ukończona.
Widać z warunku, że a jest podzielne przez b, b jest podzielne przez b 1, co oznacza, że pojęcie podzielności wyraża się w ten sposób: za = b q i b = b 1 q 1 , skąd a = b 1 (q 1 q) , gdzie q i q 1 są liczbami całkowitymi. Zgodnie z regułą mnożenia liczb całkowitych mamy, że iloczyn liczb całkowitych jest liczbą całkowitą o równości postaci a = b 1 · (q 1 · q) . Widać, że b1 jest dzielnikiem a. nierówność 1< b 1 < b Nie pasuje, ponieważ otrzymujemy, że b jest najmniejszym dodatnim dzielnikiem a innym niż 1.
Twierdzenie 2
Liczb pierwszych jest nieskończenie wiele.
Dowód 2
Załóżmy, że bierzemy skończoną liczbę liczb naturalnych n i oznaczamy je jako p 1 , p 2 , … , p n . Rozważmy wariant znalezienia liczby pierwszej innej niż wskazane.
Rozważmy liczbę p, która jest równa p 1 , p 2 , … , p n + 1 . Nie równa się każdej z liczb odpowiadających liczbom pierwszym postaci p 1 , p 2 , … , p n . Liczba p jest pierwsza. Wtedy twierdzenie uważa się za udowodnione. Jeśli jest złożony, to musimy przyjąć notację p n + 1 i pokaż niezgodność dzielników z dowolnym z p 1 , p 2 , … , p n .
Gdyby tak nie było, to na podstawie własności podzielności iloczynu p 1 , p 2 , … , p n , otrzymujemy, że byłoby to podzielne przez p n + 1 . Zauważ, że wyrażenie p n + 1 liczba p jest dzielona, równa się sumie p 1 , p 2 , … , p n + 1 . Otrzymujemy, że wyrażenie p n + 1 drugi wyraz tej sumy, który jest równy 1, trzeba podzielić, ale jest to niemożliwe.
Można zauważyć, że wśród dowolnej liczby danych liczb pierwszych można znaleźć dowolną liczbę pierwszą. Wynika z tego, że liczb pierwszych jest nieskończenie wiele.
Ponieważ jest wiele liczb pierwszych, tabele są ograniczone do liczb 100, 1000, 10000 i tak dalej.
Sporządzając tablicę liczb pierwszych należy wziąć pod uwagę fakt, że takie zadanie wymaga sekwencyjnego sprawdzania liczb, zaczynając od 2 do 100. Jeśli nie ma dzielnika, jest on zapisywany w tabeli; jeśli jest złożony, to nie jest wprowadzany do tabeli.
Rozważmy krok po kroku.
Jeśli zaczniesz od liczby 2, to ma ona tylko 2 dzielniki: 2 i 1, co oznacza, że można ją wpisać do tabeli. Również z numerem 3. Liczba 4 jest złożona, należy ją rozłożyć na 2 i 2. Liczba 5 jest liczbą pierwszą, co oznacza, że można ją ustawić w tabeli. Zrób to do liczby 100.
Ta metoda jest niewygodna i czasochłonna. Możesz zrobić stół, ale będziesz musiał spędzić dużo czasu. Konieczne jest stosowanie kryteriów podzielności, co przyspieszy proces znajdowania dzielników.
Za najwygodniejszą uważa się metodę z wykorzystaniem sita Eratostenesa. Rzućmy okiem na poniższe tabele. Na początek zapisywane są liczby 2, 3, 4, ..., 50.
Teraz musisz wykreślić wszystkie liczby, które są wielokrotnościami 2. Wykonaj sekwencyjne przekreślenie. Otrzymujemy tablicę postaci:
Przejdźmy do wykreślania liczb, które są wielokrotnościami 5. Otrzymujemy:
Przekreślamy liczby, które są wielokrotnościami 7, 11. Wreszcie tabela wygląda
Przejdźmy do sformułowania twierdzenia.
Twierdzenie 3
Najmniejszy dodatni i różny od 1 dzielnik liczby podstawowej a nie przekracza a , gdzie a jest pierwiastkiem arytmetycznym podanej liczby.
Dowód 3
Konieczne jest oznaczenie b jako najmniejszego dzielnika liczby złożonej a. Istnieje liczba całkowita q , gdzie a = b · q , i mamy to , że b ≤ q . Nierówność formy b > q ponieważ warunek jest naruszony. Obie strony nierówności b ≤ q należy pomnożyć przez dowolną dodatnią liczbę b różną od 1 . Otrzymujemy, że b b ≤ b q , gdzie b 2 ≤ a i b ≤ a .
Z udowodnionego twierdzenia widać, że wykreślenie liczb w tabeli prowadzi do tego, że trzeba zacząć od liczby równej b 2 i spełniającej nierówność b 2 ≤ a . Oznacza to, że jeśli wykreślisz liczby, które są wielokrotnościami 2, proces rozpocznie się od 4, a te, które są wielokrotnościami 3, od 9 i tak dalej, aż do 100.
Zestawienie takiej tablicy na podstawie twierdzenia Eratostenesa mówi, że po wykreśleniu wszystkich liczb złożonych pozostaną liczby pierwsze nieprzekraczające n. W przykładzie, w którym n = 50, mamy to n = 50. Stąd otrzymujemy, że sito Eratostenesa przesiewa wszystkie liczby złożone, których wartość nie jest większa niż wartość pierwiastka z 50. Wyszukiwanie numerów odbywa się poprzez przekreślanie.
Przed rozwiązaniem należy dowiedzieć się, czy liczba jest pierwsza, czy złożona. Często stosuje się kryteria podzielności. Spójrzmy na to na poniższym przykładzie.
Przykład 1
Udowodnij, że 898989898989898989 jest liczbą złożoną.
Rozwiązanie
Suma cyfr podanej liczby wynosi 9 8 + 9 9 = 9 17 . Więc liczba 9 17 jest podzielna przez 9, w oparciu o znak podzielności przez 9. Wynika z tego, że jest złożony.
Takie znaki nie są w stanie udowodnić pierwszości liczby. Jeśli konieczna jest weryfikacja, należy podjąć inne kroki. Najbardziej odpowiednim sposobem jest wyliczanie liczb. Podczas tego procesu można znaleźć liczby pierwsze i złożone. Oznacza to, że wartości liczbowe nie powinny przekraczać . Oznacza to, że liczbę a należy rozłożyć na czynniki pierwsze. jeśli to prawda, to liczbę a można uznać za pierwszą.
Przykład 2
Określ liczbę złożoną lub pierwszą 11723.
Rozwiązanie
Teraz musisz znaleźć wszystkie dzielniki dla liczby 11723. Trzeba oszacować 11723 .
Stąd widzimy, że 11723< 200 , то 200 2 = 40 000 i 11 723< 40 000 . Получаем, что делители для 11 723 меньше числа 200 .
Aby dokładniej oszacować liczbę 11723, należy napisać wyrażenie 108 2 = 11 664, oraz 109 2 = 11 881 , To 108 2 < 11 723 < 109 2 . Wynika z tego, że 11723< 109 . Видно, что любое число, которое меньше 109 считается делителем для заданного числа.
Po rozłożeniu otrzymujemy, że 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 to wszystkie liczby pierwsze. Cały ten proces można przedstawić jako dzielenie przez kolumnę. To znaczy, podziel 11723 przez 19. Liczba 19 jest jednym z jej czynników, ponieważ otrzymujemy dzielenie bez reszty. Przedstawmy podział według kolumny:
Wynika z tego, że 11723 jest liczbą złożoną, ponieważ oprócz siebie i 1 ma dzielnik 19 .
Odpowiedź: 11723 to liczba złożona.
Jeśli zauważysz błąd w tekście, zaznacz go i naciśnij Ctrl+Enter
Wszystkie inne liczby naturalne nazywamy złożonymi. Liczba naturalna 1 nie jest ani pierwszą, ani złożoną.
Przykład
Ćwiczenia. Które z poniższych liczb naturalnych są pierwsze:
Odpowiedź.
Faktoryzacja liczby
Reprezentacja liczby naturalnej jako iloczynu liczb naturalnych nazywa się faktoryzacja. Jeżeli w rozkładzie na czynniki liczby naturalnej wszystkie czynniki są liczbami pierwszymi, to taki rozkład na czynniki nazywamy faktoryzacja pierwsza.
Twierdzenie
(podstawowe twierdzenie arytmetyki)
Każdą liczbę naturalną inną niż 1 można rozłożyć na czynniki pierwsze, i to w unikalny sposób (jeśli zidentyfikujemy rozkłady i , gdzie i są liczbami pierwszymi).
Łącząc identyczne czynniki pierwsze w rozkładzie liczby, otrzymujemy tzw. rozkład kanoniczny liczby:
gdzie , są różnymi liczbami pierwszymi i są liczbami naturalnymi.
Przykład
Ćwiczenia. Znajdź kanoniczne rozwinięcie liczb:
Rozwiązanie. Aby znaleźć kanoniczne rozwinięcie liczb, musisz najpierw rozłożyć je na czynniki pierwsze, a następnie połączyć te same czynniki i zapisać ich iloczyn jako stopień z naturalnym wykładnikiem:
Odpowiedź.
Odniesienie historyczne
Jak określić, która liczba jest liczbą pierwszą, a która nie? Najpowszechniejszą metodę znajdowania wszystkich liczb pierwszych w dowolnym przedziale liczbowym zaproponowano w III wieku. pne mi. Eratostenesa (metoda nazywa się „sitem Eratostenesa”). Załóżmy, że musimy ustalić, która z liczb jest pierwsza. Zapisujemy je w rzędzie i skreślamy co drugą liczbę spośród tych, które występują po cyfrze 2 - wszystkie są złożone, ponieważ są wielokrotnościami liczby 2. Pierwsza z pozostałych niewykreślonych liczb - 3 - jest liczbą pierwszą. Skreśl co trzecią liczbę spośród tych, które występują po cyfrze 3; kolejna z nieskrzyżowanych liczb - 5 - również będzie liczbą pierwszą. Na tej samej zasadzie skreślamy co piątą liczbę od cyfr następujących po cyfrze 5 i generalnie każde -e od cyfr następujących po cyfrze . Wszystkie pozostałe nie przekreślone liczby będą pierwsze.
Wraz ze wzrostem liczb pierwszych stają się one coraz rzadsze. Jednak już starożytni doskonale zdawali sobie sprawę z tego, że jest ich nieskończenie wiele. Dowód na to znajduje się w Elementach Euklidesa.
Liczba pierwsza jest liczbą naturalną (całkowitą dodatnią), która jest podzielna bez reszty tylko przez dwie liczby naturalne: przez siebie i przez siebie. Innymi słowy, liczba pierwsza ma dokładnie dwa dzielniki naturalne: i samą liczbę.
Z definicji zbiór wszystkich dzielników liczby pierwszej jest dwuelementowy, tj. jest zestawem.
Zbiór wszystkich liczb pierwszych jest oznaczony symbolem . Zatem na mocy definicji zbioru liczb pierwszych możemy napisać: .
Ciąg liczb pierwszych wygląda następująco:
Podstawowe twierdzenie arytmetyki
Podstawowe twierdzenie arytmetyki twierdzi, że każdą liczbę naturalną większą od jedności można przedstawić jako iloczyn liczb pierwszych i to w unikalny sposób, aż do rzędu czynników. Zatem liczby pierwsze są elementarnymi „cegiełkami” zbioru liczb naturalnych.
Dekompozycja liczby naturalnej title="Renderowane przez QuickLaTeX.com" height="13" width="42" style="vertical-align: -1px;"> в произведение простых чисел называют !} kanoniczny:
gdzie jest liczbą pierwszą i . Na przykład rozwinięcie kanoniczne liczby naturalnej wygląda następująco: .
Reprezentacja liczby naturalnej jako iloczynu liczb pierwszych nazywana jest również reprezentacją faktoryzacja liczb.
Własności liczb pierwszych
Sito Eratostenesa
Jednym z najbardziej znanych algorytmów wyszukiwania i rozpoznawania liczb pierwszych jest sito Eratostenesa. Tak więc ten algorytm został nazwany na cześć greckiego matematyka Eratostenesa z Cyreny, który jest uważany za autora algorytmu.
Aby znaleźć wszystkie liczby pierwsze mniejsze od podanej liczby, stosując metodę Eratostenesa, należy wykonać następujące kroki:
Krok 1. Wypisz w rzędzie wszystkie liczby naturalne od dwóch do , tj. .
Krok 2 Przypisz zmiennej wartość, czyli wartość równą najmniejszej liczbie pierwszej.
Krok 3 Usuń z listy wszystkie liczby od do wielokrotności , czyli liczby: .
Krok 4 Znajdź pierwszą nieskrzyżowaną liczbę na liście większą niż , i przypisz wartość tej liczby do zmiennej.
Krok 5 Powtarzaj kroki 3 i 4, aż zostanie osiągnięta żądana liczba.
Proces stosowania algorytmu będzie wyglądał następująco:
Wszystkie pozostałe nieskrzyżowane liczby na liście na końcu procesu stosowania algorytmu będą zbiorem liczb pierwszych od do .
Hipoteza Goldbacha
Okładka książki „Wujek Petros i hipoteza Goldbacha”
Pomimo faktu, że liczby pierwsze były badane przez matematyków od dawna, dziś wiele związanych z nimi problemów pozostaje nierozwiązanych. Jednym z najbardziej znanych nierozwiązanych problemów jest Hipoteza Goldbacha, który jest sformułowany w następujący sposób:
- Czy to prawda, że każdą liczbę parzystą większą od dwóch można przedstawić jako sumę dwóch liczb pierwszych (binarna hipoteza Goldbacha)?
- Czy to prawda, że każdą liczbę nieparzystą większą od 5 można przedstawić jako sumę trzech liczb pierwszych (hipoteza Goldbacha o trójskładniku)?
Należy powiedzieć, że trójskładnikowa hipoteza Goldbacha jest szczególnym przypadkiem binarnej hipotezy Goldbacha lub, jak mówią matematycy, trójskładnikowa hipoteza Goldbacha jest słabsza niż binarna hipoteza Goldbacha.
Hipoteza Goldbacha stała się szeroko znana poza społecznością matematyczną w 2000 roku dzięki chwytowi marketingowemu Bloomsbury USA (USA) oraz firm wydawniczych Faber and Faber (Wielka Brytania). Wydawnictwa te, po wydaniu książki „Wujek Petros i hipoteza Goldbacha”, obiecały wypłacić nagrodę w wysokości 1 miliona dolarów w ciągu 2 lat od daty publikacji książki temu, kto udowodni hipotezę Goldbacha. Czasami wspomniana nagroda od wydawców jest mylona z nagrodami za rozwiązanie Problemów Nagrody Milenijnej. Nie popełnij błędu, hipoteza Goldbacha nie jest wymieniana przez Clay Institute jako Millennium Challenge, chociaż jest ściśle związana z hipoteza Riemanna jedno z Wyzwań Milenijnych.
Książka „Proste liczby. Długa droga do nieskończoności
Okładka książki „Świat matematyki. Proste liczby. Długa droga do nieskończoności
Dodatkowo polecam lekturę fascynującej książki popularnonaukowej, której adnotacja brzmi: „Poszukiwanie liczb pierwszych jest jednym z najbardziej paradoksalnych problemów w matematyce. Naukowcy próbują go rozwiązać od kilku tysiącleci, ale zdobywając nowe wersje i hipotezy, ta tajemnica wciąż pozostaje nierozwiązana. Pojawianie się liczb pierwszych nie podlega żadnemu systemowi: powstają one spontanicznie w szeregu liczb naturalnych, ignorując wszelkie próby matematyków identyfikacji wzorców w ich sekwencji. Ta książka pozwoli czytelnikowi prześledzić ewolucję idei naukowych od starożytności do współczesności i przybliży najciekawsze teorie poszukiwania liczb pierwszych.
Dodatkowo zacytuję początek drugiego rozdziału tej książki: „Liczby pierwsze są jednym z ważnych tematów, które cofają nas do samych początków matematyki, a następnie drogą coraz większej złożoności prowadzą nas do cięcia krawędź współczesnej nauki. Dlatego bardzo przydatne byłoby prześledzenie fascynującej i złożonej historii teorii liczb pierwszych: jak dokładnie się rozwinęła, jak dokładnie zebrano fakty i prawdy, które są obecnie uważane za ogólnie akceptowane. W tym rozdziale zobaczymy, jak pokolenia matematyków dokładnie badały liczby naturalne w poszukiwaniu reguły przewidującej pojawienie się liczb pierwszych, reguły, która w trakcie poszukiwań stawała się coraz bardziej nieuchwytna. Przyjrzymy się także kontekstowi historycznemu: w jakich warunkach pracowali matematycy iw jakim stopniu ich praca wiązała się z praktykami mistycznymi i półreligijnymi, które w niczym nie przypominają metod naukowych stosowanych w naszych czasach. Niemniej jednak powoli i z trudem przygotowywano grunt pod nowe poglądy, które zainspirowały Fermata i Eulera w XVII i XVIII wieku”.
- Tłumaczenie
Własności liczb pierwszych po raz pierwszy badali matematycy starożytnej Grecji. Matematycy szkoły pitagorejskiej (500-300 pne) interesowali się przede wszystkim mistycznymi i numerologicznymi właściwościami liczb pierwszych. Jako pierwsi wpadli na pomysły dotyczące liczb doskonałych i przyjaznych.
Liczba doskonała ma swoje własne dzielniki równe samej sobie. Na przykład właściwymi dzielnikami liczby 6 są: 1, 2 i 3. 1 + 2 + 3 = 6. Dzielnikami liczby 28 są 1, 2, 4, 7 i 14. Ponadto 1 + 2 + 4 + 7 + 14 = 28.
Liczby nazywamy przyjaznymi, jeśli suma dzielników właściwych jednej liczby jest równa drugiej i odwrotnie - np. 220 i 284. Można powiedzieć, że liczba doskonała jest przyjazna samej sobie.
Do czasu pojawienia się dzieła Euklidesa „Początki” w 300 rpne. Kilka ważnych faktów dotyczących liczb pierwszych zostało już udowodnionych. W IX Księdze Elementów Euklides udowodnił, że istnieje nieskończona liczba liczb pierwszych. Nawiasem mówiąc, jest to jeden z pierwszych przykładów użycia dowodu przez zaprzeczenie. Dowodzi również Podstawowego Twierdzenia Arytmetyki - każdą liczbę całkowitą można przedstawić w unikalny sposób jako iloczyn liczb pierwszych.
Pokazał też, że jeśli liczba 2 n -1 jest liczbą pierwszą, to liczba 2 n -1 * (2 n -1) będzie doskonała. Inny matematyk, Euler, w 1747 roku był w stanie wykazać, że wszystkie liczby nawet doskonałe można zapisać w tej postaci. Do dziś nie wiadomo, czy istnieją nieparzyste liczby doskonałe.
W roku 200 p.n.e. Grecki Eratostenes wymyślił algorytm znajdowania liczb pierwszych zwany Sitem Eratostenesa.
A potem nastąpił wielki przełom w historii badań nad liczbami pierwszymi związany ze średniowieczem.
Kolejnych odkryć dokonał już na początku XVII wieku matematyk Fermat. Udowodnił hipotezę Alberta Girarda, że dowolną liczbę pierwszą postaci 4n+1 można jednoznacznie zapisać jako sumę dwóch kwadratów, a także sformułował twierdzenie, że dowolną liczbę można przedstawić jako sumę czterech kwadratów.
Opracował nową metodę faktoryzacji dla dużych liczb i zademonstrował ją na liczbie 2027651281 = 44021 × 46061. Udowodnił również Małe Twierdzenie Fermata: jeśli p jest liczbą pierwszą, to p = a modulo p będzie prawdziwe dla dowolnej liczby całkowitej a.
To stwierdzenie dowodzi połowy tego, co było znane jako „hipoteza chińska” i pochodzi sprzed 2000 lat: liczba całkowita n jest liczbą pierwszą wtedy i tylko wtedy, gdy 2n-2 jest podzielne przez n. Druga część hipotezy okazała się fałszywa - na przykład 2341 - 2 jest podzielne przez 341, chociaż liczba 341 jest złożona: 341 = 31 × 11.
Małe twierdzenie Fermata było podstawą wielu innych wyników teorii liczb i metod sprawdzania, czy liczby są pierwsze, z których wiele jest nadal w użyciu.
Fermat korespondował obszernie z jemu współczesnymi, zwłaszcza z mnichem imieniem Marin Mersenne. W jednym ze swoich listów przypuszczał, że liczby w postaci 2 n + 1 zawsze będą pierwsze, jeśli n jest potęgą dwójki. Przetestował to dla n = 1, 2, 4, 8 i 16 i był pewien, że gdy n nie jest potęgą dwójki, liczba niekoniecznie jest pierwsza. Liczby te nazywane są liczbami Fermata i dopiero 100 lat później Euler wykazał, że następna liczba, 232 + 1 = 4294967297, jest podzielna przez 641, a zatem nie jest liczbą pierwszą.
Liczby postaci 2 n - 1 również były przedmiotem badań, ponieważ łatwo wykazać, że jeśli n jest złożone, to sama liczba również jest złożona. Liczby te nazywane są liczbami Mersenne'a, ponieważ aktywnie je studiował.
Ale nie wszystkie liczby postaci 2 n - 1, gdzie n jest liczbą pierwszą, są liczbami pierwszymi. Na przykład 2 11 - 1 = 2047 = 23 * 89. Po raz pierwszy odkryto to w 1536 roku.
Przez wiele lat liczby tego rodzaju dawały matematykom największe znane liczby pierwsze. Że liczba M 19 została udowodniona przez Cataldiego w 1588 r. i przez 200 lat była największą znaną liczbą pierwszą, dopóki Euler nie udowodnił, że M 31 jest również liczbą pierwszą. Ten rekord utrzymywał się przez kolejne sto lat, a następnie Lucas wykazał, że M 127 jest liczbą pierwszą (a to już liczba 39 cyfr), a następnie badania kontynuowano wraz z pojawieniem się komputerów.
W 1952 roku udowodniono pierwszeństwo liczb M 521 , M 607 , M 1279 , M 2203 i M 2281 .
Do 2005 roku znaleziono 42 liczby pierwsze Mersenne'a. Największy z nich, M 25964951 , składa się z 7816230 cyfr.
Praca Eulera wywarła ogromny wpływ na teorię liczb, w tym na liczby pierwsze. Rozszerzył Małe Twierdzenie Fermata i wprowadził funkcję φ. Rozłożył piątą liczbę Fermata na czynniki 2 32 +1, znalazł 60 par przyjaznych liczb i sformułował (ale nie udowodnił) kwadratowego prawa wzajemności.
Jako pierwszy wprowadził metody analizy matematycznej i rozwinął analityczną teorię liczb. Udowodnił, że nie tylko szereg harmoniczny ∑ (1/n), ale także szereg postaci
1/2 + 1/3 + 1/5 + 1/7 + 1/11 +…
Otrzymane przez sumę wielkości odwrotnych do liczb pierwszych, również rozbieżne. Suma n wyrazów szeregu harmonicznego rośnie w przybliżeniu jak log(n), podczas gdy drugi szereg rozchodzi się wolniej, jak log[log(n)]. Oznacza to, że np. suma odwrotności wszystkich znalezionych do tej pory liczb pierwszych da tylko 4, chociaż szeregi wciąż są rozbieżne.
Na pierwszy rzut oka wydaje się, że liczby pierwsze są rozmieszczone wśród liczb całkowitych raczej losowo. Na przykład wśród 100 liczb bezpośrednio przed 10000000 jest 9 liczb pierwszych, a wśród 100 liczb bezpośrednio po tej wartości są tylko 2. Ale w dużych segmentach liczby pierwsze są rozmieszczone dość równomiernie. Ich dystrybucją zajmowali się Legendre i Gauss. Gauss powiedział kiedyś znajomemu, że w dowolnych wolnych 15 minutach zawsze liczy liczby pierwsze w kolejnych 1000 liczbach. Pod koniec życia policzył wszystkie liczby pierwsze do 3 milionów. Legendre i Gauss w równym stopniu obliczyli, że dla dużych n gęstość liczb pierwszych wynosi 1/log(n). Legendre oszacował liczbę liczb pierwszych między 1 a n jako
π(n) = n/(log(n) - 1,08366)
I Gauss - jako całka logarytmiczna
π(n) = ∫ 1/log(t) dt
Z przedziałem integracji od 2 do n.
Twierdzenie o gęstości liczb pierwszych 1/log(n) jest znane jako twierdzenie o liczbach pierwszych. Próbowali to udowodnić przez cały XIX wiek, a Czebyszew i Riemann poczynili postępy. Połączyli to z Hipotezą Riemanna, dotychczas nieudowodnionym przypuszczeniem o rozkładzie zer funkcji zeta Riemanna. Gęstość liczb pierwszych została jednocześnie udowodniona przez Hadamarda i de la Vallée-Poussina w 1896 roku.
W teorii liczb pierwszych wciąż istnieje wiele nierozwiązanych pytań, z których niektóre mają wiele setek lat:
- hipoteza bliźniaczych liczb pierwszych - o nieskończonej liczbie par liczb pierwszych, które różnią się od siebie o 2
- Hipoteza Goldbacha: każdą liczbę parzystą, począwszy od 4, można przedstawić jako sumę dwóch liczb pierwszych
- Czy istnieje nieskończona liczba liczb pierwszych postaci n 2 + 1 ?
- czy zawsze można znaleźć liczbę pierwszą między n 2 a (n + 1) 2 ? (fakt, że zawsze istnieje liczba pierwsza między n a 2n udowodnił Czebyszew)
- Czy istnieje nieskończona liczba liczb pierwszych Fermata? czy są jakieś liczby pierwsze Fermata po 4?
- czy istnieje ciąg arytmetyczny kolejnych liczb pierwszych dla dowolnej długości? na przykład dla długości 4: 251, 257, 263, 269. Maksymalna znaleziona długość to 26 .
- Czy istnieje nieskończona liczba zestawów trzech kolejnych liczb pierwszych w ciągu arytmetycznym?
- n 2 - n + 41 jest liczbą pierwszą dla 0 ≤ n ≤ 40. Czy istnieje nieskończona liczba takich liczb pierwszych? To samo pytanie dotyczy wzoru n 2 - 79 n + 1601. Te liczby są pierwsze dla 0 ≤ n ≤ 79.
- Czy istnieje nieskończona liczba liczb pierwszych postaci n# + 1? (n# jest wynikiem mnożenia wszystkich liczb pierwszych mniejszych od n)
- Czy istnieje nieskończona liczba liczb pierwszych postaci n# -1?
- Czy istnieje nieskończona liczba liczb pierwszych postaci n! +1?
- Czy istnieje nieskończona liczba liczb pierwszych postaci n! - 1?
- jeśli p jest liczbą pierwszą, czy 2 p -1 zawsze nie zalicza się do czynników liczb pierwszych do kwadratu
- Czy ciąg Fibonacciego zawiera nieskończoną liczbę liczb pierwszych?
Największe bliźniacze liczby pierwsze to 2003663613 × 2 195000 ± 1. Składają się z 58711 cyfr i zostały znalezione w 2007 roku.
Największa silnia liczba pierwsza (postaci n! ± 1) to 147855! - 1. Składa się z 142891 cyfr i został znaleziony w 2002 roku.
Największa pierwotna liczba pierwsza (liczba postaci n# ± 1) to 1098133# + 1.
Liczby są różne: naturalne, naturalne, wymierne, całkowite i ułamkowe, dodatnie i ujemne, zespolone i pierwsze, nieparzyste i parzyste, rzeczywiste itp. Z tego artykułu dowiesz się, czym są liczby pierwsze.
Jakie liczby nazywane są angielskim słowem „prosty”?
Bardzo często dzieci w wieku szkolnym nie wiedzą, jak odpowiedzieć na jedno z pozornie prostych pytań w matematyce, o to, czym jest liczba pierwsza. Często mylą liczby pierwsze z liczbami naturalnymi (czyli liczbami, których ludzie używają do liczenia przedmiotów, podczas gdy w niektórych źródłach zaczynają się od zera, aw innych - od jedynki). Ale to są dwa zupełnie różne pojęcia. Liczby pierwsze to liczby naturalne, to znaczy liczby całkowite i dodatnie, które są większe od jeden i które mają tylko 2 dzielniki naturalne. W tym przypadku jeden z tych dzielników to dana liczba, a drugi to jednostka. Na przykład trzy jest liczbą pierwszą, ponieważ nie jest podzielna przez żadną liczbę inną niż sama siebie i jedynkę.
Liczby złożone
Przeciwieństwem liczb pierwszych są liczby złożone. Są też naturalne, także większe od jednego, ale mają nie dwa, ale więcej dzielników. Na przykład liczby 4, 6, 8, 9 itd. są liczbami naturalnymi, złożonymi, ale nie pierwszymi. Jak widać, są to w większości liczby parzyste, ale nie wszystkie. Ale „dwa” to liczba parzysta i „pierwsza liczba” w szeregu liczb pierwszych.
Podsekwencja
Aby zbudować szereg liczb pierwszych, konieczne jest dokonanie wyboru spośród wszystkich liczb naturalnych, biorąc pod uwagę ich definicję, to znaczy trzeba działać na zasadzie sprzeczności. Konieczne jest rozważenie każdej z naturalnych liczb dodatnich na temat tego, czy ma ona więcej niż dwa dzielniki. Spróbujmy zbudować szereg (sekwencję), który składa się z liczb pierwszych. Lista zaczyna się od dwóch, potem pojawia się trójka, ponieważ jest podzielna tylko przez siebie i jeden. Rozważ liczbę cztery. Czy ma dzielniki inne niż cztery i jeden? Tak, ta liczba to 2. Więc cztery nie jest liczbą pierwszą. Pięć też jest liczbą pierwszą (oprócz 1 i 5 nie jest podzielna przez żadną inną liczbę), ale szóstka jest podzielna. Ogólnie rzecz biorąc, jeśli prześledzisz wszystkie liczby parzyste, zauważysz, że oprócz „dwóch” żadna z nich nie jest pierwsza. Z tego wnioskujemy, że liczby parzyste, z wyjątkiem dwóch, nie są pierwsze. Kolejne odkrycie: wszystkie liczby podzielne przez trzy, z wyjątkiem samej trójki, parzyste lub nieparzyste, również nie są pierwsze (6, 9, 12, 15, 18, 21, 24, 27 itd.). To samo dotyczy liczb podzielnych przez pięć i siedem. Cały ich zestaw również nie jest prosty. Podsumujmy. Tak więc wszystkie liczby nieparzyste, z wyjątkiem jednego i dziewięciu, należą do prostych liczb jednocyfrowych, a tylko „dwa” od parzystych. Same dziesiątki (10, 20,... 40 itd.) nie są liczbami pierwszymi. Liczby pierwsze dwucyfrowe, trzycyfrowe itp. można zdefiniować w oparciu o powyższe zasady: jeśli nie mają innych dzielników niż siebie i jedynkę.
Teorie dotyczące własności liczb pierwszych
Istnieje nauka, która bada właściwości liczb całkowitych, w tym liczb pierwszych. Jest to gałąź matematyki, która nazywa się wyższą. Oprócz własności liczb całkowitych zajmuje się również liczbami algebraicznymi, przestępnymi, a także funkcjami różnego pochodzenia związanymi z arytmetyką tych liczb. W badaniach tych oprócz metod elementarnych i algebraicznych stosuje się również metody analityczne i geometryczne. W szczególności badanie liczb pierwszych zajmuje się „teorią liczb”.
Liczby pierwsze to „cegiełki” liczb naturalnych
W arytmetyce istnieje twierdzenie zwane twierdzeniem głównym. Zgodnie z nim każdą liczbę naturalną, z wyjątkiem jedności, można przedstawić jako iloczyn, którego czynnikami są liczby pierwsze, a kolejność czynników jest jednoznaczna, co oznacza, że sposób reprezentacji jest jednoznaczny. Nazywa się to rozkładem liczby naturalnej na czynniki pierwsze. Istnieje inna nazwa tego procesu - faktoryzacja liczb. Wychodząc z tego, liczby pierwsze można nazwać „materiałem budowlanym”, „blokami” do konstruowania liczb naturalnych.
Szukaj liczb pierwszych. Testy prostoty
Wielu naukowców różnych czasów próbowało znaleźć zasady (systemy) wyszukiwania listy liczb pierwszych. Nauka zna systemy zwane sitami Atkina, sitami Sundartama, sitami Eratostenesa. Jednak nie dają one żadnych znaczących wyników, a do znalezienia liczb pierwszych stosuje się prosty test. Algorytmy tworzyli również matematycy. Nazywa się je testami pierwszości. Na przykład istnieje test opracowany przez Rabina i Millera. Jest używany przez kryptografów. Istnieje również test Kayala-Agrawala-Saskena. Jednak pomimo wystarczającej dokładności jest bardzo trudny do obliczenia, co umniejsza jego wartość praktyczną.
Czy zbiór liczb pierwszych ma granicę?
Fakt, że zbiorem liczb pierwszych jest nieskończoność, został opisany w książce „Początki” przez starożytnego greckiego naukowca Euklidesa. Powiedział tak: „Wyobraźmy sobie przez chwilę, że liczby pierwsze mają granicę. Następnie pomnóżmy je przez siebie i dodajmy jeden do iloczynu. Liczba uzyskana w wyniku tych prostych operacji nie może być podzielna przez żadną z serii liczb pierwszych, ponieważ reszta zawsze będzie równa jeden. A to oznacza, że istnieje inna liczba, której nie ma jeszcze na liście liczb pierwszych. Dlatego nasze założenie nie jest prawdziwe, a ten zbiór nie może mieć granicy. Oprócz dowodu Euklidesa istnieje bardziej współczesna formuła podana przez osiemnastowiecznego szwajcarskiego matematyka Leonharda Eulera. Według niego suma, odwrotność sumy pierwszych n liczb, rośnie w nieskończoność wraz ze wzrostem liczby n. A oto wzór twierdzenia o rozkładzie liczb pierwszych: (n) rośnie jak n/ln (n).
Jaka jest największa liczba pierwsza?
Mimo to Leonard Euler był w stanie znaleźć największą liczbę pierwszą swoich czasów. To jest 2 31 - 1 = 2147483647. Jednak do 2013 roku obliczono kolejną najdokładniejszą największą na liście liczb pierwszych - 2 57885161 - 1. Nazywa się to liczbą Mersenne'a. Zawiera około 17 milionów cyfr dziesiętnych. Jak widać liczba znaleziona przez naukowca z XVIII wieku jest od tej kilkukrotnie mniejsza. Tak powinno być, bo Euler wykonał te obliczenia ręcznie, ale naszemu rówieśnikowi prawdopodobnie pomógł komputer. Co więcej, numer ten uzyskano na Wydziale Matematyki jednego z amerykańskich wydziałów. Liczby nazwane na cześć tego naukowca przechodzą przez test pierwszości Luca-Lehmera. Jednak nauka nie chce na tym poprzestać. Electronic Frontier Foundation, założona w 1990 roku w Stanach Zjednoczonych Ameryki (EFF), zaoferowała nagrodę pieniężną za znalezienie dużych liczb pierwszych. A jeśli do 2013 roku nagrodę przyznawano tym naukowcom, którzy znajdą je od 1 do 10 milionów liczb dziesiętnych, to dziś liczba ta sięga od 100 milionów do 1 miliarda. Nagrody wahają się od 150 do 250 tysięcy dolarów amerykańskich.
Nazwy specjalnych liczb pierwszych
Te liczby, które zostały znalezione dzięki algorytmom stworzonym przez niektórych naukowców i przeszły test prostoty, nazywane są specjalnymi. Tutaj jest kilka z nich:
1. Mersin.
4. Cullena.
6. Mills i in.
Prostotę tych liczb, nazwanych na cześć powyższych naukowców, ustala się za pomocą następujących testów:
1. Łukasz-Lemer.
2. Pepina.
3. Rizel.
4. Billhart – Lehmer – Selfridge i inni.
Współczesna nauka nie poprzestaje na tym i prawdopodobnie w niedalekiej przyszłości świat pozna nazwiska tych, którym udało się wygrać nagrodę w wysokości 250 000 dolarów, znajdując największą liczbę pierwszą.