• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Krótko o liczbach pierwszych

    10.09.2011. 13:47
    opublikowane przez: Przemysaw Szydzik

    Liczby pierwsze, choć znane od wczesnych lat szkolnej edukacji, są bardzo ciekawymi obiektami matematycznymi. Kryją w sobie wiele tajemnic, których odkrycie nie udało się dotychczas nawet najtęższym umysłom świata.

    Dla porządku przypomnijmy, że liczbą pierwszą nazywamy każdą liczbę naturalną , która ma dokładnie dwa dzielniki: oraz . Przyjrzyjmy się nieco bliżej zbiorowi liczb pierwszych. Na pewno każdy potrafi wypisać kilka liczb pierwszych. Gdybyśmy chcieli wypisać kilka liczb pierwszych zaczynając od największej, to mielibyśmy spory problem. Tak naprawdę jest to niemożliwe, ponieważ liczb pierwszych jest nieskończenie wiele, a co za tym idzie nie możemy wskazać największej. Nie ma problemu z wyznaczeniem jednak najmniejszej liczby pierwszej, czyli . Wtedy kolejnymi liczbami pierwszymi są: . Przy okazji zauważmy, że jest jedyną wypisaną dotychczas liczbą parzystą, która jest pierwsza. Czy na pewno nie ma więcej?

    Nie, ponieważ gdyby takowa istniała " na przykład liczba " to dzieliłaby się oprócz oraz również przez , co przeczyłoby warunkowi definicji.

    1. Ile jest liczb pierwszych?


    Odpowiedź na to pytanie padła już powyżej, a znana jest już od dosyć dawna, bo od ok 300 r. przed Chrystusem. Wówczas to Euklides, jako jeden z pierwszych (choć w literaturze przyjmuje się raczej, że jako pierwszy) udowodnił matematycznie niemożliwość istnienia największej liczby pierwszej, a co jest równoważne stwierdzeniu, że zbiór liczb pierwszych jest nieskończony.

    Zanim spróbujemy uzasadnić dlaczego liczb pierwszych jest nieskończenie wiele, przywołam jedno ważne twierdzenie. Nosi ono nazwę Podstawowego twierdzenia arytmetyki. Chociaż w nazwie wyczuwa się, że jest ono rzeczywiście kluczowe dla całej arytmetyki, to w szkole raczej się o nim nie wspomina.

    Podstawowe twierdzenie arytmetyki
    Każda liczba naturalna większa od 1 ma jednoznaczne (z dokładnością do kolejności czynników) przedstawienie w postaci iloczynu liczb pierwszych.

    Jednoznaczność trzeba rozumieć w ten sposób, że jeśli dowolna liczba np. będąca iloczynem liczb pierwszych innego rozkładu już nie ma z dokładnością do kolejności czynników, to znaczy mówimy, że .

    Podstawowe twierdzenie arytmetyki pomoże w uzasadnieniu twierdzenia Euklidesa.
    Aby łatwiej się pisało o zbiorze liczb pierwszych ustalmy raz na zawsze (czyli do końca artykułu), że przez oznaczać będziemy zbiór (wszystkich, nie tylko wybranych) liczb pierwszych.

    Przypuśćmy, że zbiór jest skończony i składa się z dokładnie liczb pierwszych:
    Utwórzmy liczbę naturalną postaci:

    Z podstawowego twierdzenia arytmetyki wynika, że n ma jednoznaczny rozkład na czynniki pierwsze. Zauważmy przy tym, że żadna ze zbioru nie dzieli . Wynika stąd, że istnieją inne liczby pierwsze występujące w rozkładzie liczby . A zatem zbiór nie zawiera wszystkich liczb pierwszych.

    Wniosek: zbiór nie jest zbiorem skończonym.

    Liczby pierwsze mają swoje zastosowanie w naszej codzienności. To właśnie liczby pierwsze wykorzystywane w pomysłach matematyków oraz przekute klawiaturami informatyków w programy komputerowe zapewniają bezpieczne szyfrowanie informacji w Internecie.

    2. Jak sprawdzić czy liczba jest pierwsza?


    Odpowiedź na to pytanie jest dość prosta " należy tylko sprawdzić czy nie ma podzielników większych różnych od i samej tej liczby. Powstaje jednak pytanie, jak długo sprawdzać podzielność. Na pewno nie trzeba sprawdzać większych niż , co wynika wprost z definicji. Jeśli przypatrzymy się, jak układają się pary liczb, których iloczyn jest równy , to łatwo wywnioskować, że wystarczy jednak sprawdzić liczby od do .

    Podamy stwierdzenie, które pozwoli jeszcze bardziej ograniczyć liczbę sprawdzeń:


    Dowód:
    Przypuśćmy, że żadna liczba naturalna nie jest podzielnikiem liczby oraz jest liczbą złożoną. Zatem , gdzie .
    Wówczas są możliwe dwie wykluczające się wypadki:
    (1) ;
    (2) .
    Z dowolności i nie musimy rozważać sytuacji, gdy (ponieważ albo obie liczby są równe albo jedna jest większa). Jeśli zachodzi (1), to . Ale zakładaliśmy, że nie jest podzielnikiem liczby , więc otrzymujemy sprzeczność. Zatem warunek (1) nie może zachodzić.
    Jeśli zachodzi (2), to i , co jest sprzeczne z założeniem. Zatem warunek (2) również nigdy nie zachodzi. Stąd niemożliwym jest aby n było liczbą złożoną, więc jest liczbą pierwszą.

    3. Jak znaleźć wszystkie liczby pierwsze?


    Pytanie jest oczywiście nieco na wyrost. Nie da się znaleźć wszystkich liczb pierwszych, ale potrafimy znaleźć wszystkie liczby pierwsze mniejsze od pewnej, ustalonej liczby . Można posłużyć się ciekawym z punktu widzenia informatyki algorytmem, który nazywany jest sitem Erastotenesa i pochodzi z czasów starożytnych. Polega ona na usuwaniu (przesiewaniu przez sito) krotności kolejnych liczb pierwszych. Pozostają wówczas wyłącznie liczby pierwsze nie większe niż .

    Przeanalizujmy działanie sita dla liczb naturalnych z przedziału [2, 30]:


    Załączony film prezentuje działanie algorytmu, który zaproponował Eratostenes. Zauważmy, że potrzebowaliśmy aż 10 kroków (czyli kolorowań dziewięciu liczb) żeby wyznaczyć wszystkie liczby pierwsze z tego przedziału. Powstaje naturale pytanie, czy można szybciej. Okazuje się, że tak. Zauważmy, że od pewnego momentu nie wykreślamy już żadnych liczb, tylko kolorujemy (tzn. uznajemy za pierwsze) te, które pozostały. Z pomocą przychodzi stwierdzenie z punktu 2. Zastosowanie go do sita Eratostenesa pozwala ograniczyć liczbę wykreśleń (a tym samym sprawdzeń) do liczb nie większych niż .
    Na załączonym filmie widać, że jako ostatnią wykreślamy krotność liczby 5. Zauważmy przy tym, że , co potwierdza naszą obserwację. Dzięki temu wystarczyłoby wykreślać krotności tylko trzech kolejnych liczb a resztę, która pozostała uznać za liczby pierwsze. Jest to znaczne uproszczenie w stosunku do początkowych 10 kroków.

    Dowód naszej obserwacji pozostawiamy czytelnikowi.

    Czy wiesz ĹĽe...? (beta)
    Arytmetyka teoretyczna (z łac. arithmos – liczba) – nauka o liczbach. Zajmuje się definiowaniem różnych rodzajów liczb, działań na nich oraz wyjaśnianiem związków pomiędzy zdefiniowanymi zbiorami liczbowymi. Podstawowym zbiorem jest zbiór liczb naturalnych. Za pomocą liczb naturalnych można skonstruować kolejno: liczby całkowite, wymierne, rzeczywiste i zespolone. Pozostałe, bardziej skomplikowane rodzaje liczb powstają przez rozszerzenie poprzedniego rodzaju liczb. Tak więc definicje wszystkich rodzajów liczb opierają się na definicji liczb naturalnych, a co za tym idzie, problem niesprzeczności różnych systemów liczbowych sprowadza się do problemu niesprzeczności teorii liczb naturalnych. Najmniejsza wspólna wielokrotność dwóch lub więcej liczb naturalnych a1, a2,... ,an - najmniejsza liczba naturalna ze zbioru wszystkich liczb naturalnych, których dzielnikiem jest każda z liczb a1,...,an, i na przykład dla liczb 15 i 240 jest to liczba 240, a dla liczb 192 i 348 - liczba 5568. Najmniejszą wspólną wielokrotność oznacza się często symbolem NWW(a1,...,an). Funkcja multiplikatywna – W teorii liczb, funkcję arytmetyczną f określoną na zbiorze liczb naturalnych nazywamy multiplikatywną, jeżeli dla wszystkich względnie pierwszych liczb m, n spełniony jest warunek

    Chen Jingrun (ur. 22 maja 1933, zm. 19 marca 1996) - chiński matematyk którego dziedziną badań była teoria liczb. Największym jego osiągnięciem było tzw. twierdzenie Chena stanowiące słabszą wersję słynnej hipotezy Goldbacha. Według powyższej hipotezy każdą liczbę naturalną parzystą przedstawić można jako sumę dwóch liczb pierwszych. Jest to przypuszczenie do dnia dzisiejszego nie udowodnione. Twierdzenie Chena różni się jedynie tym że drugi składnik sumy może być liczbą półpierwszą. Twierdzenie Chena zostało udowodnione w roku 1966 i nie jest hipotezą. Istnieje także pojęcie liczby pierwszej Chena która ma postać p+2 gdzie p jest dowolną liczbą pierwszą, p+2 natomiast może być liczbą pierwszą bądź półpierwszą. Słaba hipoteza Goldbacha to przypuszczenie w teorii liczb, które mówi, że każda liczba naturalna nieparzysta i większa od 7 jest sumą trzech nieparzystych liczb pierwszych (niekoniecznie różnych).

    Liczba pierwsza Sophie Germain – w teorii liczb dowolna liczba pierwsza p, dla której liczba 2p+1 również jest pierwsza (np. 23, ponieważ 2 · 23 + 1 = 47 jest liczbą pierwszą); liczby te zostały nazwane na cześć Marie-Sophie Germain (ciąg A005384 w OEIS). Przypuszczalnie istnieje nieskończenie wiele liczb pierwszych Sophie Germain, jednak do 2012 roku jest to problem otwarty. Największą znaną do 2012 roku liczbą pierwszą Sophie Germain jest 18543637900515·2-1, a jej zapis dziesiętny wymaga 200701 cyfr; została znaleziona w kwietniu 2012 przez Philipa Bliedunga, podczas rozproszonych obliczeń w ramach projektu PrimeGrid, przy użyciu programów TwinGen oraz LLR. Zbiór liczb rzeczywistych – uzupełnienie zbioru liczb wymiernych. Zbiór liczb rzeczywistych zawiera m.in. liczby naturalne, ujemne, całkowite, pierwiastki liczb dodatnich, wymierne, niewymierne, przestępne, itd. Z drugiej strony na liczby rzeczywiste można też patrzeć jak na szczególne przypadki liczb zespolonych.

    Regularne liczby pierwsze – w teorii liczb jest to klasa liczb pierwszych wprowadzona przez niemieckiego matematyka Ernsta Kummera. Podstawowe twierdzenie arytmetyki – ważne twierdzenie teorii liczb o rozkładzie liczb naturalnych na czynniki pierwsze.

    Liczba taksówkowa – w matematyce, enta liczba taksówki, zwykle oznaczana Ta(n) albo Taxicab(n), jest zdefiniowana jako najmniejsza liczba, która może być wyrażona jako suma dwóch sześcianów na n różnych sposobów. G. H. Hardy i E. M. Wright udowodnili w 1954, że takie liczby istnieją dla wszystkich dodatnich liczb całkowitych n. Jednakże dowód nie pomaga w wyznaczaniu kolejnych liczb Ta(n). Do tej pory znanych jest dwanaście kolejnych liczb taksówkowych.

    Liczby niewymierne – liczby rzeczywiste nie będące liczbami wymiernymi, czyli takie liczby rzeczywiste których nie można zapisać w postaci ilorazu dwóch liczb: liczby całkowitej przez liczbę naturalną różną od zera.

    Liczby Carmichaela to w teorii liczb takie złożone liczby naturalne, dla których teza Małego Twierdzenia Fermata jest prawdziwa.

    Dodano: 10.09.2011. 13:47  


    Najnowsze