Иван Матвеевич Виноградов - Основы теории чисел: Учебное пособие

Q

^ " И. M. ВИНОГРАДОВ
-и

/

it

Знание I
Уверенность f
Успех •

Т

Л - Г ч ' , ' J • .i
и

ЛУЧШИЕ КЛАССИЧЕСКИЕ

УЧЕБНИКИ

МАТЕМАТИКА

И. М. ВИНОГРАДОВ

ОСНОВЫ
ТЕОРИИ
ЧИСЕЛ
У Ч Е Б Н О Е

П О С О Б И Е

Издание одиннадцатое,
стереотипное

лека
X

САНКТ-ПЕТЕРБУРГ • МОСКВА • КРАСНОДАР
2006

ББК 22.13
В 49
В 49

Виноградов И. М.
Основы теории чисел: Учебное пособие. 11-е изд.,
стер. — СПб.: Издательство «Лань», 2006. — 176 с. —
(Учебники для вузов. Специальная литература).
ISBN 5-8114-0535-9
В книге и з л а г а ю т с я основы теории ч и с е л в объеме университетского курса. Д л я студентов математических специальностей
университетов и педвузов, аспирантов, н а у ч н ы х работников в
области математики.

ББК 22.13

Иван

Матвеевич

ВИНОГРАДОВ

ОСНОВЫ ТЕОРИИ ЧИСЕЛ
УЧЕБНОЕ
ПОСОБИЕ
Издание одиннадцатое,
стереотипное
Генеральный директор А Л. Кноп. Директор издательства О. В. Смирнова
Худояеественный редактор С. Л. Шапиро
Л Р № 065466 от 21.10.97
Гигиенический сертификат 78.01.07.953.П.001665.03.02
от 18.03.2002 г., выдан ЦП^Н в СПб
Вздательство «ЛАНЬ»
1ал@1рЫ.8рЪ.ги; www.lanpbl.spb.ru
192029, Санкт-Петербург, Общественный пер., 5.
ИзЗательство: тел./факс: (812)567-29-35, 567-05-97, 567-92-72;
рЫ@]]^1.8рЬ.ги; print€)pbl.8pb.ni
Книги издательства «Лань*
можно приофести в оптовых книготорговых организациях:
ООО «ЛАНЬ-ТРБЙД». 192029, Санкт-Петербург, ул. Крупской, 13,
тел./факс: (812)567-54-93, тел.: (812)567-86-78, (812)567-14-45,
567-85-82, 567-85-91; trade@IanpbUpb.ru; www.laniA)Upb.ru/price.htm
ООО «ЛАНЬ-ПРЕСС». 109263, Москва, 7-я ул. Текстильщиков, 6/19,
тел.: (095)178-65-85,178-57-04; lanpress@ultimanet.ru
ООО «ЛАНЬ-ЮГ». 350072, Краснодар, ул. Жлобы, 1/1, тел.: (861)274-10-35;
Iankrd98@mail.ru
Подписано в печать 20.10.05.
Бумага о^хжтаая. Формат 84 х 1081/,
Печать офсетная. Усл. п. л. 9,24. TiipiUK 2000 экз.
Заказ №3086
Отпечатано с готовых днапозитпвов
в О А О « П И К «Офсет»
660075, г. Красноярск, ул. Республики, я 51

Обложка
С. ШАПИРО.
А.
Охраняется законом РФ об авторском
праве. Воспроизведение всей книги или
любой ее части запрещается без письпенного разрешения издателя. Любые
попытки нарушения закона будут преследоеаться в судебном порядке.

ЛАПШИН

© Издательство «Лань», 2006
© и . М. Виноградов, 2006
© Издательство «Лань»,
художественное
оформление, 2006

ОГЛАВЛЕНИЕ
Из предисловия к девятому изданию
Глава

6

первая

Тесфия делимости

7

§ 1. Основные понятия и теоремы
§ 2. Общий наибольший делитель
§ 3. Общее наименьшее кратное
§ 4. Простые числа
§ 5. Единственность разложения на простые сомножители
§ 6. Непрерывные дроби и их связь с алгоритмом Евклида
Вопросы к главе I
Численные примч»ы к главе I
Г лава

вторая

Важнейшие функции в теории чвсел
§ 1. Функции [ * ] . { * }
§ 2. Мультипликативные функции
§ 3. Число делителей и сумма делителей
§ 4. Функция Мёбиуса
§ 5. Функция Эйлд)а
Вопросы к главе 11
Численные примеры к главе I I
Глава

7
9
12
13
15
18
22
24
25

•

25
26
28
29
30
32
40

третья

Сравнения

41

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

41

§ 2, Свойства сравнений, подобные свойствам равенств . .
§ 3. Дальнейшие свойства сравнений
§ 4. Полная система вычетов
§ 5. Приведенная система вычетов
§ 6. Теоремы Эйлера и Ферма
Вопросы к главе I I I
Численные примеры к главе I I I

42
44
45
46
47
48
53

4

ОГЛАВЛЕНИЕ

Глава

четвертая

Сравнения с одним неизвестным
§ t. Основные понятия
§ 2. Сравнения первой степени
§ 3. Система сравнений первой степени
§ 4. Сравнения любой степени по простому модулю . . .
§ 5. Сравнения любой степени по составному модулю . .
Вопросы к главе I V
Численные примеры к главе I V
Г лава

пят

ая

Сравнения второб

степени

§ 1. Общие теоремы
§ 2. Символ Лежандра
§ 3. Символ Якоби
§ 4. Случай составного модуля
Вопросы к главе V
Численные примеры к главе V
Глава

68
68
69
75
78
80
85

шестая

Первообразные корни и индексы
§ I . Общие теоремы
§ 2. Пернообраэные корки по модулям р « и 2 р «
§ 3. Разыскание первообразных корней по модулям р " и 2ро
§ 4. Индексы по модулям р " и 2р®
§ 5. Следствия предыдущей теории
§ 6. Индексы по модулю 2®
§ 7. Индексы по любому составному модулю
Вопросы к главе V I
Численные примеры к главе V I
Глава

86
86
87
89
90
93
95
98
102
104

седьмая

Характеры
§ I . Определения
§ 2. Важнейшие свойства --">