Содержание

Часть 1 Основы теории чисел. 2

Глава 1 Теория делимости. 2

1 Основные понятия и теоремы.. 2

2 Наибольший общий делитель. 3

3 Наименьшее общее кратное. 5

4 Простые числа.

5 Единственность разложения на простые сомножители. 7

6 Непрерывные дроби и их связь с алгоритмом Евклида. 9

Глава 2 Важнейшие функции в теории чисел. 13

1 Функции [x] и {x}. 13

2 Мультипликативные функции. 13

3 Число делителей и сумма делителей. 15

4 Функция Мёбиуса. 15

5 Функция Эйлера. 16

Глава 3 Сравнения. 18

1 Основные понятия. 18

2 Свойства сравнений, подобные свойствам равенств. 18

3 Дальнейшие свойства сравнений. 19

4 Полная система вычетов. 20

5 Приведенная система вычетов. 21

6 Теоремы Эйлера и Ферма. 21

Глава 4 Сравнения с одним неизвестным. 23

1 Основные понятия. 23

2 Сравнения первой степени. 23

3 Система сравнений первой степени. 25

4 Сравнения любой степени по простому модулю.. 26

5 Сравнения любой степени по составному модулю.. 26

Глава 5 Сравнения второй степени. 29

1 Общие теоремы.. 29

2 Символ Лежандра. 29

3 Символ Якоби. 33

4 Случай составного модуля. 35

Глава 6 Первообразные корни и индексы.. 37

1 Общие теоремы.. 37

2 Первообразные корни по модулям p^α и 2р^α 37

3 Разыскание первообразных корней по модулям р^α в 2р^α 39

4 Индексы по модулям р^α в 2р^α 40

5 Следствия предыдущей теории. 41

6 Индексы по модулю 2^α 43

7 Индексы по любому составному модулю.. 45

Глава 7 Характеры.. 48

1 Определения. 48

2 Важнейшие свойства характеров. 48

Часть 1