Рибенбойм: Маленькая книга больших простых чисел

Paulo Ribenboim: Mała księga wielkich liczb pierwszych

tytuł oryginału: The Little Book of Big Primes

przekład: Jerzy Browkin

Stan dobry. Zauważone defekty :

• dedykacja na stronie kontrtytułowej
• minimalne uszkodzenia okładki

Z okładki (s.4)

„Jeśli matematyka jest królową nauk (a jest!), to teoria liczb jest królową matematyki. To jej właśnie jest poświęcona ta książka. Czytając ją,

• poznasz niezwykłe fakty dotyczące liczb pierwszych;
• dowiesz się o niebanalnych metodach sprawdzania, czy liczba jest pierwsza;
• znajdziesz odpowiedź na pytanie o istnienie funkcji, której wartościami są liczby pierwsze;
• poznasz różne rodzaje liczb pierwszych;
• dowiesz się, jak są rozmieszczone liczby pierwsze wśród innych liczb;
• poznasz też rozważania heurystyczne dotyczące liczb pierwszych i metody probabilistyczne badania ich.

Książka jest napisana prostym, żywym językiem. Jej autor Paulo Ribenboim, uważany w świecie matematycznym za prawdziwego współczesnego guru teorii liczb, nie stroni także od żartu. Chciałby, żeby przy czytaniu jego dzieła »… każdy miłośnik liczb — początkujący student, nauczyciel, matematyk na emeryturze, inżynier czy hazardzista komputerowy — dał się wciągnąć w rozmyślania nad piękną teorią liczb pierwszych i tajemnicami, które w sobie kryje«. Pragnie, by Czytelnik »ćwiczył swój umysł i palce — i to w tej kolejności, a nie odwrotnie«. Mamy nadzieję, że Jego marzenia się spełnią.

To naprawdę świetna książka, a poza tym doskonały przykład znakomitej popularyzacji matematyki.”

Z okładki (s. 2)

„Paulo Ribenboim urodził się w Brazylii. Ma stopień doktora matematyki, który uzyskał w 1957 r. na University of Sao Paulo. W tym samym czasie został jednym z pierwszych profesorów w Instituto de Matematica Pura e Aplicata w Rio de Janeiro. Od 1962 r. do emerytury (przez 32 lata) wykładał w Queen’s University w Kingston, w Kanadzie. Zajmował się algebrą i teorią liczb. W 1995 r. za artykuł »Prime Number Records«, zamieszczony w College Mathematics Journal, otrzymał nagrodę Towarzystwa Matematycznego Ameryki (MAA), ufundowaną przez znakomitego matematyka George’a Pólyę.

Jest autorem 130 prac naukowych i 13 książek, z których dwie: »13 Lectures on Fermat’s Last Theorem« i »The Book of Prime Number Records« są znane na całym świecie.

Lubi podróżować i słuchać muzyki klasycznej. Interesuje się sztuką.”

Przedmowa do polskiego wydania

„Książka ta jest skróconą i odpowiednio zaktualizowaną wersją mojej książki »The Book of Prime Number Records«. Przypomina bonsai, które ma wszystkie cechy normalnego drzewa i chociaż jest mała, pragnie wzbudzić zainteresowanie. Wydaje się, że prosi:

»Kup mnie, czytaj mnie. Chcę stać się nałogiem dla Twojego umysłu i podobnie jak narkotyk wywoływać wizje liczb dużych i małych, wyczyniających dziwne pląsy. Chcę, abyś dokonywał odkryć i robił przypuszczenia. Chcę, abyś rozpamiętywał, podziwiał i starał się wnikać w tajemnice liczb pierwszych«.

Do tego kuszenia dodam od siebie:

Mam nadzieję, że młodzi oraz emeryci, a także jeszcze nie będący całkiem na emeryturze, jak również niezupełnie młodzi polscy miłośnicy matematyki poczują się szczęśliwi, gdy będą czytali te stronice.

Nie byłoby tego polskiego przekładu bez pełnej poświęcenia i znajomości rzeczy pracy mojego szanownego kolegi, Jerzego Browkina, wobec którego jestem zobowiązany i pełen wdzięczności.”

— Paulo Ribenboim

Od tłumacza

„W książce tej autor przedstawił różne rekordy dotyczące liczb pierwszych. Jednak w dobie komputerów takie rekordy mają na ogół bardzo krótki żywot. W czasie tłumaczenia tej książki ukazała się kolejna jej wersja: »The New Book of Prime Number Records« (Springer, Berlin 1996), o ponad dwa razy większej objętości i o znacznie rozszerzonej bibliografii. Zawiera ona aktualniejsze informacje, z których część została uwzględniona w niniejszym przekładzie. Czytelnika, który jest głębiej zainteresowany tą tematyką, zachęcam do zajrzenia również do tej aktualniejszej wersji.

Zapewne zanim ukaże się ten polski przekład, znów pewne z rekordów zostaną pobite.”

Przedmowa

„Książka ta mogłaby mieć tytuł: »Wybór z księgi rekordów liczb pierwszych«. Wolałem jednak taki, który przede wszystkim zachęciłby Cię do zajrzenia do niej, a może i do kupienia (mam taką nadzieję)!

[…]

Książka ta nie różni się jednak od swego pierwowzoru. Jak bonsai, które ma wszystkie podstawowe cechy normalnego drzewa, tak i ona powinna wywrzeć na Tobie wielkie wrażenie. Mówiąc słowami Johna Brillharta, pragnę, by była równie »niebezpieczna« jak tamta księga. Chciałbym, żeby każdy miłośnik liczb — początkujący student, nauczyciel, matematyk na emeryturze, inżynier czy hazardzista komputerowy — dał się wciągnąć w rozmyślania nad piękną teorią liczb pierwszych i tajemnicami, które w sobie kryje. Pragnę, aby ćwiczył swój umysł i palce — i to w tej kolejności, a nie odwrotnie.

Nie chciałbym jednak, żebyś będąc już specjalistą od teorii liczb, zaglądał do tej książeczki. Prawdopodobnie nie wziąłem Cię pod uwagę jako potencjalnego jej czytelnika, co oczywiście może sprawić Ci przykrość. Ale nie martw się — masz już przecież swoją książkę. Teraz przyszła kolej na czytelników, którzy najczęściej drobnymi kroczkami, ale i niekiedy wielkimi krokami, będą zgłębiać naukę o liczbach.”

— Paulo Ribenboim

Spis treści

Wskazówki dla czytelnika

Wykaz oznaczeń

Wstęp

1. Ile jest właściwie liczb pierwszych?

  1.1. Dowód Euklidesa

  1.2. I Goldbach to udowodnił!

  1.3. Dowód Eulera

  1.4. Dowód Thuego

  1.5. Dowód Washingtona

  1.6. Dowód Fürstenberga

  1.7. Ciągi euklidesowe

  Bibliografia

2. Jak rozpoznać, czy liczba naturalna jest pierwsza?

  2.1. Sito Eratostenesa

  2.2. Kilka podstawowych twierdzeń o kongruencjach

    2.2.1. Małe twierdzenie Fermata i pierwiastki pierwotne modulo liczba pierwsza

    2.2.2. Twierdzenie Wilsona

    2.2.3. Własności Giugi, Wolstenholme’a, Manna i Shanksa

    2.2.4. Potęga liczby pierwszej dzieląca silnię

    2.2.5. Chińskie twierdzenie o resztach

    2.2.6. Funkcja Eulera

    2.2.7. Ciągi dwumianów

    2.2.8. Reszty kwadratowe

  2.3. Klasyczne testy pierwszości oparte na kongruencjach

  2.4. Ciągi Lucasa

  2.5. Testy pierwszości oparte na ciągach Lucasa

  2.6. Liczby Fermata

  2.7. Liczby Mersenne’a

  2.8. Liczby pseudopierwsze

    2.8.1. Liczby pseudopierwsze przy podstawie 2

    2.8.2. Liczby pseudopierwsze przy podstawie a (psp(a))

    2.8.3. Liczby pseudopierwsze Eulera przy podstawie a (epsp(a))

    2.8.4. Liczby silnie pseudopierwsze przy podstawie a (spsp(a))

  2.9. Liczby Carmichaela

  2.10. Liczby pseudopierwsze Lucasa

    2.10.1. Liczby pseudopierwsze Fibonacciego

    2.10.2. Liczby pseudopierwsze Lucasa (ℓpsp(P, Q))

    2.10.3. Liczby pseudopierwsze Eulera-Lucasa (eℓpsp(P, Q)) i liczby silnie pseudopierwsze Lucasa (sℓpsp(P, Q))

    2.10.4. Liczby Carmichaela-Lucasa

  2.11. Ostatni podrozdział poświęcony badaniu pierwszości i rozkładaniu na czynniki

    2.11.1. Koszt przeprowadzenia testu

    2.11.2. Dalsze testy pierwszości

    2.11.3. Liczby pierwsze tytaniczne

    2.11.4. Rozkłady na czynniki pierwsze

    2.11.5. Kryptografia z kluczem publicznym

  Bibliografia

3. Czy istnieją funkcje określające liczby pierwsze?

  3.1. Funkcje spełniające warunek (a)

  3.2. Funkcje spełniające warunek (b)

  3.3. Funkcje spełniające warunek (c)

  Bibliografia

4. Jak są rozmieszczone liczby pierwsze?

  4.1. Szybkość wzrostu funkcji π(x)

    4.1.1. Rozwój historyczny

    4.1.2. Sumy zawierające funkcję Möbiusa

    4.1.3. Rozmieszczenie wartości funkcji Eulera

    4.1.4. Tablice liczb pierwszych

    4.1.5. Dokładna wartość funkcji π(x) i jej porównanie z x/log(x), Li(x) i R(x)

    4.1.6. Zera niebanalne funkcji ζ(s)

    4.1.7. Obszary bez zer funkcji ζ(s) i oszacowanie błędu w twierdzeniu o liczbach pierwszych

  4.2. n-ta liczba pierwsza i odstępy między kolejnymi liczbami pierwszymi

    4.2.1. Pewne własności funkcji π(x)

    4.2.2. n-ta liczba pierwsza

    4.2.3. Odstępy między kolejnymi liczbami pierwszymi

    4.2.4. Jakie mogą być odstępy między kolejnymi liczbami pierwszymi?

  4.3. Liczby pierwsze bliźniacze

  4.4. Liczby pierwsze w ciągu arytmetycznym

    4.4.1. Jest ich nieskończenie wiele

    4.4.2. Najmniejsza liczba pierwsza w ciągu arytmetycznym

    4.4.3. Ciągi arytmetyczne złożone z liczb pierwszych

  4.5. Słynna hipoteza Goldbacha

  4.6. Rozmieszczenie liczb pseudopierwszych i liczb Carmichaela

    4.6.1. Rozmieszczenie liczb pseudopierwszych

    4.6.2. Rozmieszczenie liczb Carmichaela

    4.6.3. Rozmieszczenie liczb pseudopierwszych Lucasa

  Bibliografia

5. Jakie rozpatrywano szczególne rodzaje liczb pierwszych?

  5.1. Liczby pierwsze regularne

  5.2. Liczby pierwsze Zofii Germain

  5.3. Liczby pierwsze Wiefericha

  5.4. Liczby pierwsze Wilsona

  5.5. Liczby pierwsze utworzone z jedynek i liczby analogiczne

  5.6. Liczby postaci k × 2ⁿ ± 1

  5.7. Liczby pierwsze w liniowych ciągach rekurencyjnych drugiego rzędu

  Bibliografia

6. Rozważania heurystyczne i metody probabilistyczne badania liczb pierwszych

  6.1. Wartości wielomianów liniowych będące liczbami pierwszymi

  6.2. Wartości wielomianów dowolnych stopni będące liczbami pierwszymi

  6.3. Wielomiany, które przyjmują kolejno wiele wartości złożonych

  6.4. Partitio numerorum

  Bibliografia

Zakończenie

Bibliografia ogólna

Tablica liczb pierwszych mniejszych od 10000

Galimatias

Wykaz tablic

Wykaz rekordów

Skorowidz osobowy

Skorowidz rzeczowy