Spis treści Wstęp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
1. Podzielność i algorytm Euklidesa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
1.1. Podzielność . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2. Algorytm Euklidesa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2. Liczby pierwsze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
3. Kongruencje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
3.1. Własności . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2. Klasyczne twierdzenia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25 29
4. Równania diofantyczne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.1. Równania liniowe z dwiema niewiadomymi . . . . . . . . . . . . . . . . . . . . . . . . 4.2. Równania liniowe z n niewiadomymi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3. Równania stopnia drugiego . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4. Równania rozmaite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35 38 41 45
5. Rozwiązywanie kongruencji . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 5.1. Kongruencje liniowe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2. Kongruencje kwadratowe i symbol Legendre’a . . . . . . . . . . . . . . . . . . . . . 5.3. Algebraiczne własności układów reszt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4. Kongruencje rozmaite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53 55 65 72
6. Liczby pierwsze – ciąg dalszy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 6.1. Wzory i algorytmy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 6.2. Informacje i hipotezy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 7. Funkcje arytmetyczne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
91
7.1. Podstawowe funkcje arytmetyczne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 7.2. Liczby doskonałe, liczby zaprzyjaźnione i inne . . . . . . . . . . . . . . . . . . . . . 103 7.3. Własności algebraiczne funkcji arytmetycznych . . . . . . . . . . . . . . . . . . . . 108 7.4. Własności analityczne funkcji arytmetycznych . . . . . . . . . . . . . . . . . . . . . 116 7.5. Własności analityczne funkcji π(x) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 Bibliografia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 Skorowidz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 Skorowidz Mathematica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135