Markowe wykłady z matematyki Teoria liczb

Opis

Markowe wykłady z matematyki Teoria liczb

Wydawnictwo: GIS

Autorzy: Marek Zakrzewski

 

Na wykładach analizy matematycznej student poznaje metody analizy, czasem także ciekawe wyniki uzyskane za pomocą tych metod. Na wykładach algebry – metody algebry, z rzadka jakieś zastosowania. Teoria liczb jest zupełnie inna. Składa się z prostych, intrygujących pytań o otaczający nas świat liczb i zdumiewająco wyrafinowanych odpowiedzi z użyciem metod analizy, algebry – abstrakcyjnej i liniowej, czasem metod kombinatorycznych i geometrycznych. Teoria liczb łączy prostotę pytań z bogactwem metod. Na tym polega jej urok. Materiał książki obejmuje m.in. kongruencje, podstawy kryptografii i algorytmy randomizacyjne, rozmieszczenie liczb pierwszych, reszty kwadratowe, prawo wzajemności i sumy kwadratów, równania diofantyczne i wstęp do krzywych eliptycznych.

 

Spis treści

Wstęp

I Euklides, Fermat i kongruencje 1

1 Liczby pierwsze 4

1.1 Twierdzenie Euklidesa i sito Eratostenesa . .  4

1.2 Algorytm Euklidesa i jego konsekwencje . . . 7

1.3 Euklides . . 12

2 Kongruencje i ich zastosowania 13

2.1 Kongruencje .  13

2.2 Dwa klasyczne twierdzenia: Wilsona i Fermata .  17

2.3 Myśl lokalnie – wnioskuj globalnie . . 20

2.4 Fermat . .. . 23

3 Równania i wielomiany w arytmetyce modularnej .. 25

3.1 Chińskie twierdzenie o resztach . . .. 25

3.2 Twierdzenia Lagrange’a i jego zastosowania . . . 28

4 Funkcja Eulera i pierwiastki pierwotne 31

4.1 Funkcja Eulera i twierdzenie Eulera . . .  31

4.2 Rząd elementu i pierwiastki pierwotne . . .34

II Kryptografia i algorytmy randomizacyjne 37

5 Krótki kurs kryptografii 40

5.1 Szyfry symetryczne i uzgadnianie klucza . .. 40

5.2 RSA . . . 42

5.3 Protokół ElGamala . .. 46

6 Rozpoznawanie pierwszości .. 48

6.1 Rozpoznawanie pierwszości . . . 48

6.2 Złożoność obliczeniowa i algorytmy deterministyczne . . 53

7 Faktoryzacja 56

7.1 Algorytm Fermata i Dixona . . . . 56

7.2 Dwa algorytmy Pollarda . . . . 60

III Rozmieszczenie liczb pierwszych 65

8 Twierdzenie Eulera i gęstość zbioru liczb pierwszych …68

8.1 Liczby pierwsze rozmieszczone są dość gęsto . .. 68

8.2 Liczby pierwsze rozmieszczone są dość rzadko* . . 71

8.3 Euler . . . 73

9 Dwa „łatwe” twierdzenia 75

9.1 Twierdzenie Czebyszewa i hipoteza Sierpińskiego .. 75

9.2 Twierdzenie Dirichleta – najprostsze przypadki . . 78

9.3 Czebyszew i Sierpiński . . . . . . . . . . . . . . . . . . . . . . . 82

10 Kilka bardzo prostych pytań 83

10.1 Cztery problemy Landaua . . . . . . . . . . . . . . . . . . . . . 83

10.2 Wielomiany a liczby pierwsze . . . . . . . . . . . . . . . . . . . 85

10.3 Chen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

11 Twierdzenie o rozmieszczeniu liczb pierwszych 89

11.1 Twierdzenie o rozmieszczeniu liczb pierwszych i jego konsekwencje 90

11.2 TRLP: idea dowodu* . . . . . . . . . . . . . . . . . . . . . . . . 93

11.3 Hipoteza Riemanna i liczby pierwsze . . . . . . . . . . . . . . . 96

11.4 Riemann i Dirichlet . . . . . . . . . . . . . . . . . . . . . . . . . 97

IV Sumy kwadratów i prawo wzajemności 99

12 Dwa twierdzenia o sumach kwadratów 101

12.1 Kraty w R i lemat Minkowskiego . . . . . . . . . . . . . . . . 101

12.2 Twierdzenie Fermata-Eulera i okolice . . . . . . . . . . . . . . . 104

12.3 Twierdzenia Lagrange’a . . . . . . . . . . . . . . . . . . . . . . 107

12.4 Lagrange . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

13 Twierdzenia Hilberta-Waringa i Cauchy’ego 112

13.1 Sumy potęg i twierdzenie Hilberta-Waringa . . . . . . . . . . . 112

13.2 Liczby wielokątne i twierdzenie Cauchy’ego . . . . . . . . . . . 115

14 Reszty kwadratowe i symbol Legendre’a 117

14.1 Reszty kwadratowe i kryterium Eulera . . . . . . . . . . . . . . 117

14.2 Symbol Legendre’a i jego własności . . . . . . . . . . . . . . . . 119

14.3 Lemat Gaussa i jego zastosowania . . . . . . . . . . . . . . . . 122

14.4 Legendre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

15 Prawo wzajemności i jego zastosowania 126

15.1 Prawo wzajemności i lemat Eisensteina . . . . . . . . . . . . . . 127

15.2 Zastosowania prawa wzajemności . . . . . . . . . . . . . . . . . 130

15.3 Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134

16 Kongruencje kwadratowe i kryptografia 135

16.1 Kongruencje kwadratowe . . . . . . . . . . . . . . . . . . . . . 135

16.2 Obliczanie pierwiastków kwadratowych* . . . . . . . . . . . . . 138

17 Symbol Jacobiego 140

17.1 Symbol Jacobiego i jego własności . . . . . . . . . . . . . . . . 140

17.2 Zastosowania symbolu Jacobiego . . . . . . . . . . . . . . . . . 143

17.3 Jacobi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147

18 Liczby całkowite Gaussa 148

18.1 Pierścień Z[i] . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148

18.2 Elementy pierwsze i jednoznaczność rozkładu . . . . . . . . . . 151

18.3 Twierdzenie Fermata-Eulera i liczba rozkładów . . . . . . . . . 155

18.4 Minkowski . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157

V Równania diofantyczne i krzywe eliptyczne 159

19 Równanie Pitagorasa i wielkie twierdzenie Fermata 162

19.1 Równanie Pitagorasa . . . . . . . . . . . . . . . . . . . . . . . . 162

19.2 Wielkie twierdzenie Fermata – pierwszy krok . . . . . . . . . . . 166

19.3 Diofantos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169

20 Równanie Pella 170

20.1 Trzy bardzo różne zadania . . . . . . . . . . . . . . . . . . . . . 171

20.2 Rozwiązanie równania Pella: pierwsze podejście . . . . . . . . . 173

20.3 Kwestia istnienia* . . . . . . . . . . . . . . . . . . . . . . . . . 177

21 Ułamki łańcuchowe i równanie Pella 180

21.1 Ułamki łańcuchowe . . . . . . . . . . . . . . . . . . . . . . . . . 180

21.2 Aproksymacje, równanie Pella i trzoda Heliosa . . . . . . . . . 185

22 Krzywe eliptyczne 189

22.1 Krzywe eliptyczne . . . . . . . . . . . . . . . . . . . . . . . . . 189

22.2 Krzywe eliptyczne nad ciałami skończonymi . . . . . . . . . . . 196

23 Krzywe eliptyczne a równania diofantyczne 198

23.1 Klasyfikacja krzywych algebraicznych . . . . . . . . . . . . . . . 198

23.2 Równanie Bacheta-Mordella . . . . . . . . . . . . . . . . . . . . 200

23.3 Problem liczb kongruentnych . . . . . . . . . . . . . . . . . . . 202

23.4 Liczby Hardy’ego-Ramanujana* . . . . . . . . . . . . . . . . . . 205

23.5 Ramanujan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208

24 Wielkie twierdzenie Fermata: ekspresem przez historię 209

24.1 Od Fermata do Kummera — i trochę dalej . . . . . . . . . . . 209

24.2 Wielkie twierdzenie Fermata i krzywe eliptyczne . . . . . . . . 212

25 Równania diofantyczne i twierdzenie G¨odla 215

25.1 Twierdzenie G¨odla . . . . . . . . . . . . . . . . . . . . . . . . . 216

25.2 Równania diofantyczne i twierdzenie Matjasiewicza . . . . . . . 220

25.3 Peano i G¨odel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223

Epilog 225

Uwagi o literaturze 229

Odpowiedzi i wskazówki 231

Indeks 243