Основы теории чисел: Учебное пособие [Иван Матвеевич Виноградов] (pdf) читать онлайн

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. Важнейшие свойства характеров
Вопросы к главе V I I
Численные примеры к главе V I I
Решения

^
54
54
57
58
60
63
67

вопросов

106
106
106
Ш
114
115

Решения к главе I
Решения к главе I I

115
ИЧ

Решения к главе П1
Решения к главе I V

132
142

ОГЛАВЛЕНИЕ

Решения к

главе

V

б

; .

Решения к главе V I

. .
.

Решения к главе V I I

к
к
к
к
к

156
159

Ответы к численным примерам
Ответы
Ответы
Ответы
Ответы
Ответы

147

165

главе I
главе II
главе I I I
главе I V
главе V

165
165
165
165
166

Ответы к главе V I
Ответы к главе V I I

166
167

Таблицы индексов
Таблица

простых

разных корней

168
чисел О, т — ц е л о е , m > I и * пробегает целые положительные числа, не делящиеся на щ-ю степень целого, превосходящего 1. Доказать, что

ВОПРОСЫ к ГЛАВЕ
3. Пусть положительные а и р
[с«]:

л:=1.2. ...;

III

33

таковы, что
2

[Р^/].

образуют, вместе взятые, все числа натурального ряда без повторений. Доказать, что это имеет место тогда и только тогда, когда а
иррациональное, причем
а + р
4. а. Пусть
< = [т] и Xi, х^,
расположенные в таком порядке, чтобы числа

числа 1,2, . . . , t,

0. { « w i } , {алгг}, . . . . {олг,}, I
шли не убывая. Доказать теорему вопроса 4, Ь, гл. I, рассматривая
разности соседних чисел последнего ряда.
Ь. Пусть Ti, Т2, . . . . X]f—вещественные числа, каждое из которых не меньше 1; tti, Ог, ••., а^—вещественные. Доказать, что существуют целые l i , ^21 •lilt, не равные одновременно нулю, и целое г),
удовлетворяющие условиям:
IglK-Tl.

| l 2 l < T 2 , . . . . ||fe| 0. Доказать, что

[[«11
с

'

а"
с

в, а. Пусть а , Р, . . . , Я,—вещественные. Доказать, что

[a+P-f

+

+

+

Ь. Пусть о, Ь, . . . . I—целые положительные, a + f c + . . . +
Применяя Ь, § I , доказать, что
л1

/=«.

а\Ь\ ... 1\

есть целое число.
7. Пусть h—целое, h > О, р—простое и

1
Представляя h в виде A ^ p ^ t / ^ - f р ^ и ^ + р о ,
где
«и—наибольшее « j , не превосходящее h, р,яМя,—на1Йольшее кратное и^, не превосходящее ft, Pm-i'^m-i—наибольшее
кратное
не превосходящее ,
ft—Pm-i'^m-i—наибольшее
кратное и„_2>
не превосходящее h—Рт'^т—
и т. д., доказать, что числа с с условием, что в каноническое разложение а1 число р входит
с показателем h, существуют тогда и только тогда, когда все
Рт< Рт-1'---> Pi' Ре меньше р, причем в этом случае указанные
а суть все числа вида

a = PmP""*'^+Pm-lP'"+ •••+P1P'^+P0P+P',
где р' имеет значенияг О, 1,

р—1.

34

ВАЖНЕЙШИЕ ФУНКЦИИ В ТЕОРИИ ЧИСЕЛ

[ГЛ.

II

8, а. Пусть в интервале Q < * < ; / ? функция f (х) имеет вторую
непрерывную производную. Полагая
X

рМ= Y ~ "

W=JР
о

доказать, что

R
2

/W =

Q
Рк—все простые делители числа а.
а. Применяя теорему вопроса 17, а, доказать, что

N)» (а) = 2 1
d\a

(

т

^

)

•

38

ВАЖНЕЙШИЕ ФУНКЦИИ В ТЕОРИИ ЧИСЕЛ

[ГЛ. II

b. Доказать, что
>l)i(a)=|-«p(a).
c. Доказать, что
(—1)®

Л

•
О<

j "Р

19. Пусть г > 1, а—целое, а > О, Т ^ — ч и с л о чисел х с условиями
(дс, а ) = 1 , е—произвольное положительное постоянное,
а. Доказать, что

d\a
b. Доказать, что

с. Пусть Z > 1, я (г)—число
простых чисел, не превосходящих е,
а—произведение простых чисел, не превосходящих У ~ г .
Доказать, что

d\a

L"J

20. Пусть /г (s) > 1, а — ц е л о е , а > 0. Доказать, что

где в левой части п пробегает целые положительные числа, взаимно
простые с а, а в правой части р пробегает все простые делители
числа а
21, а. Вероятность Р того, что k целых положительных чисел
*2, • • .
будут взаимно простыми, определим как предел при
N —»- 00 вероятности Р/^ того, что будут взаимно простыми k чисел
Xi, *2. . . . . JCfc, каждому иэ которых независимо от остальных присвоено одно из значений ! . 2, . . . , N. принимаемых за равиовозможные. Применяя теорему вопроса 17, Ь, доказать, что
=
(J^))""^.
jf
Ь. Определяя вероятность Р несократимости дробн — аналогично
тому, как в вопросе а при k=2,

доказать, что
я"

22, а. Пусть г > 2 и Т — ч и с л о целых точек ( * , ф с взаимно
простыми координатами, лежащих в области ж ' + у ^ ^ г ® . Доказать,
что
In г ) .

ВОПРОСЫ к ГЛАВЕ

III

39

Ь. Пусть
и Т —число целых точек (х, у, г) с взаимно простыми координатами, лежащих в области
Доказать,
что

3^3)
23. а. Теорему 2, Ь, § 4 доказать, считая делители числа а, не
делящиеся на квадрат целого, превосходящего I , и нмеюшле 1 , 2 , . . .
простых делителей.
b. Пусть а—целое, а > l,d пробегает делители числа а, имеющие
не более чем т простых делителей. Доказать, что при т четном
^ t i W ^ ® ' ^ "Р"
нечетном У
c. При условиях теоремы с, § 4, считая все f неотрицательными
и заставляя d пробегать лишь числа, имеюшле не более чем т простых
делителей, доказать, что

в зависимости от того, будет л и т четным или нечетным.
d . Такие же, как в вопросе с, неравенства доказать при условиях
вопроса 17, а, считая все значения f(x) неотрицательными, а также
при условиях 17, Ь, считая все значения f (xi, xi
Xh) неотрицательными.
24. Пусть е — л ю б о е постоянное с условиями 0 < е < - ^ ,
г=1п//, 0 < ( 7 < / / 1 - 8 , 0 < / < 9 ,
простых чисел с условиями: p^N,
зать, что

N^8,

(9, /) = 1, n(N,
q, /)—число
p=qt + l, где t—целое.
Дока-

Д л я доказательства, полагая ft=ri-®.®8 , простые числа с указанными условиями следует рассматривать как частный случай всех
чисел с этими условиями взаимно простых с а, где а—произведение
всех простых, не превосходящих е * и не делящих д. Следует применить теорему вопроса 23, d (условия вопроса 17, а) с указанным а и
/л-=2[2 n r + I ] ,
25. Пусть k—четное:
к > О, каноническое разложение числа а
имеет вид a = p i p g . . Pk « d пробегает делители числа а с условием
О < d < У ^ . Доказать, что

d
26. Пусть k—целое, k > О, d пробегает делители числа с условием
ф(« О, (а, Т ) = 1.
M+m-i

S=

s
*=м

{/W).

где в интервале
Л ! + / n — 1 функция / ( * ) имеет непрерывные производные f (дг) и f (дг), причем выполняются условия

(а.т) = и
где

|e| О,
В—вещественное. Доказать, что

M+m-i
х=М

5, а. Пусть у 4 > 2 , fc^I н в интервале Q ^ * ^ / ? функция
/ (дс) имеет вторую непрерывную производную, удовлетворяющую
условиям

Доказать, что

0 . Обозначая
символом ( о ) численное значение разности между а и ближайшим
к а целым числом (расстояние а до ближайшего целого), доказать, что

M + P-i

2niax

f2

1 и функции М (а) м Р (а) д л я значений а = 1, 2, . . . , т — I принимают целые значения с условием
Р (а) > 0. Доказать, что
т-1

Д1(.)+Р(а)-1

1
а=1

2J
х=М(а)
/•mlnm,

О, | пробегает приведенную систему вычетов по модулю т . Доказать, что
ц(т) =

2 е

т

'

b. Пользуясь теоремой вопроса а, доказать первую из теорем с,
§ 4, гл. И (см, решение вопроса 28, а, гл. П ) .
c. Теорему вопроса а вывести, пользуясь теоремой вопроса 17.
а, гл. П .
d. Пусть
S

а. ...,

6

бдс«...а)в

— многочлен с целыми коэффициентами от г переменных х,
...
. . . , w ( r ^ I ) , а — ц е л о е , т — ц е л о е , m > О, дг, . . . , ш пробегают полные, а I , . . . , 1. Тогда, чтобы сравнение (1) имело решения, необходимо (е, § 3, гл. III),
чтобы Ь делилось на d, иначе сравнение (1) невозможно
ни при каком целом х. Предполагая поэтому b кратным d, положим a = aid, b = bid, m-tn-id. Тогда сравнение (1) бурет равносильно такому (по сокращ,ении Had):
UiX = bi {mod nil), в котором уже ( O i , и
потому
оно будет иметь одно решение по модулю т^. Пусть дс,—
наименьший неотрицательный вычет этого решения по
модулю т „ тогда все числа х, образующие это решение,
найдутся в виде
* = *x(modmi).

(2)

По модулю же т числа (2) образуют не одно решение, а
больше, именно столько решений, сколько чисел (2) найдется в ряде О, 1, 2, . . . , т — 1 наименьших неотрицательных вычетов по модулю т. Но сюда попадут следующие числа (2):
-f /Пх. Xi + 2mi

Xi +

{d—l)rni,

т. е. всего d чисел (2); следовательно, сравнение (1) имеет d решений.
d. Собирая все доказанное, получаем теорему:
Пусть la,m) — d. Сравнение ах = Ь (тойт) невозможно, если Ь не делится на d. При Ь, кратном d, сравнение
имеет d решений.
e. Обращаясь к разысканию решений сравнения (1),
мы укажем только способ, основанный на теории непрерывных дробей, причем достаточно ограничиться лишь
случаем {а, т ) = 1.

56

1ГЛ. IV

СРАВНЕНИЯ С ОДНИМ НЕИЗВЕСТНЫМ

Разлагая в непрерывную дробь отношение т:а,
I

• =