Учебное пособие Москва Издательство мцнмо 2007 удк 512. 1517. 1511. 1 Ббк 22. 14122. 161 П70 Прасолов В. В

• Название: Учебное пособие Москва Издательство мцнмо 2007 удк 512. 1517. 1511. 1 Ббк 22. 14122. 161 П70 Прасолов В. В
• Дата: 16.10.2022
• Размер: 3.28 Mb.
• Имя файла: algebra.pdf
• Тип: Учебное пособие; #736986
• страница: 51 из 71

31.62. Докажите, что если x
m
≡1 (mod p), то показатель делит число m.
31.63. а) Докажите, что каждому показателю d принадлежит не более f
(d) остатков отделения наб) Докажите, что каждому показателю d, делящему число, принадлежит ровно f
(d) остатков отделения на в) Докажите, что для любого простого числа p существует ровно f
(p
− 1) первообразных корней. а) Дано натуральное число n > 2. Докажите, что натуральное число d, для которого x
d+1
≡x (mod n) для всех целых x, существует тогда и только тогда, когда n = p
1
. . . где p
1
, . . ., p
k
— попарно различные простые числа

Условия задач
409
б) Пусть n = p
1
. . . p
k
, где p
1
, . . ., p
k
— попарно различные простые числа. Докажите, что наименьшее натуральное число d, для которого x
d+1
≡x (mod n) для всех целых равно НОК(p
1
− 1, . . . , p
k
− 1).
31.65. Пусть p — нечётное простое число.
а) Докажите, что нечётные простые делители числа делят a − 1 или имеют вид 2px + б) Докажите, что нечётные простые делители числа a
p
+ делят a + 1 или имеют вид 2px + 1.
31.66. Пусть p — нечётное простое число. Докажите, что существует бесконечно много простых чисел вида 2px + 1.
31.67. Докажите, что все простые делители числа 2 2
n
+ имеют вид 2
n+1
x
+ 1.
31.68. Докажите, что 3 является первообразным корнем по модулю простого числа p = 2
n
+ 1, где n > 1.
31.69. Пусть p — простое число и S = 1
n
+ 2
n
+ . . . + (p Докажите, что (mod если n делится на p − 1,
0 (mod если n не делится на p − 1.
31.13. Первообразные корни по составному модулю
Первообразные корни можно рассмотреть и для составного модуля. Будем называть число x первообразным корнем по модулю, если числа x, x
2
, . . . , x
f
(m)
— это все различные остатки,
взаимно простые с m. В серии задач 31.71––31.77 доказывается,
что первообразный корень по модулю m существует тогда и только тогда, когда m = 2, 4, p
a или 2p
a
, где p — нечётное простое число. Докажите, что (1 + km)
m
a
−1
≡ 1 (mod m
a
) для любого. Пусть p — простое число. Докажите, что первообразный корень по модулю p
a является также первообразным корнем по модулю p.
31.72. Пусть x — первообразный корень по простому модулю. Предположим, что x
p
a
−2
(p
−1)
6≡ 1 (mod p
a
), где a
>
2.

Глава 31. Элементы теории чисел
Докажите, что тогда x — первообразный корень по модулю. Пусть x — первообразный корень по нечётному простому модулю p. Докажите, что по крайней мере одно из чисел x и x + p является первообразным корнем по модулю. Докажите, что если x — первообразный корень по модулю p
2
, где p — нечётное простое число, то x — первообразный корень по модулю p
a для любого a
>
2.
31.75. Пусть p — нечётное простое число. Докажите, что для любого натурального существует первообразный корень по модулю 2p
a
31.76. Докажите, что первообразный корень по модулю существует тогда и только тогда, когда n 6 2.
31.77. Докажите, что если m — это не число вида 2, 4, p
a или 2p
a
, где p — нечётное простое число, то первообразных корней по модулю m не существует. Теорема Чебышева о простых числах
Пусть p
(n) — количество простых чисел, не превосходящих n.
31.78. Докажите, что lim
n
→∞
p
(n)/n
= 0 (Эйлер. Докажите, что 3
n
ln n
<
p
(n) при n > 200.
31.80. Докажите, что p
(n) < 3 ln 2
n
ln при n > Замечание. Чебышев доказал, что для достаточно больших выполняются более точные неравенства n
<
p
(n) < 1,10555
n
ln Решения. Первое решение. Согласно задаче 4.62 набор остатков отделения на p чисел a, 2a, . . . , (p − 1)a совпадает с набором, 2, . . . , p − 1. Значит, a
p
−1
· 1 · 2 · . . . · (p
− 1) ≡ 1 · 2 · . . . · (p − 1) (mod Число b = 1 · 2 · . . . · (p − 1) не делится на p, поэтому a
p
−1
≡ 1 (mod p).

Решения задач
411
Чтобы доказать это, нужно умножить обе части равенства на число, для которого bb ≡ 1 (mod Второе решение. Покажем, что для любого натурального число n
p
− n делится на p. Применим индукцию по n. При 1 утверждение очевидно. Предположим, что n
p
− n делится на p. Тогда число (n + 1)
p
− (n + 1) = C
1
p
n
p
−1
+ C
2
p
n
p
−2
+ . . . + тоже делится на p, поскольку все числа C
k
p
, где 16 k6 p−1, делятся на p задача Если число n не делится на p, то из того, что n
p
− n = n(n
p
−1
− делится наследует, что n
p
−1
− 1 делится на p.
31.2. Предположим, что одно из чисел a и b не делится на Тогда другое число тоже не делится на p. Поэтому согласно малой теореме Ферма a
p
−1
≡ 1 (mod p) и b
p
−1
≡ 1 (mod p). Значит+ b
p
−1
≡2 (mod p). С другой стороны, число a
p
−1
+ b
p
−1
= a
4k+2
+
+ b
4k+2
= (a
2
)
2k+1
+ делится на a
2
+ b
2
, поэтому оно делится на p.
31.3. Предположим, что p
1
, . . . , p
r
— все различные простые числа вида 4k + 1. Рассмотрим число (2p
1
. . . p
r
)
2
+ 1. Оно нечёт- но, поэтому все его простые делители имеют вид 4k ± 1. Согласно задаче 31.2 у этого числа не может быть простых делителей вида − 1. Остаётся заметить, что рассматриваемое число не делится на p
1
, . . . , p
r
31.4. а) Предположим, что 2
p
≡ 1 (mod q), где q — простое число. Ясно, что q 6= 2. Если q − 1 не делится на p, то наибольший общий делитель чисел q − 1 и p равен 1, поэтому существуют целые числа a и b, для которых ap + b(q − 1) = см. с. 43). Согласно малой теореме Ферма 2
q
−1
≡ 1 (mod q). Поэтому. Приходим к противо- речию.
б) Ответ. Число 2 341
− 2 = 2(2 340
− 2) = 2((2 10
)
34
− 1) делится на 10
− 1 = 1023. Далее, 1023 = 3 · 341.
31.6. По условию 2
n
− 2 = na для некоторого натурального Поэтому 2 2
n
−1
− 2 = 2(2 2
n
−2
− 1) = 2(2
na
− 1). Это число делится на 1.
31.7. а) Среди чисел 1, 2, . . . , p
n
− 1 на p делятся p
n
−1
− 1 чисел,
а именно, числа p, 2p, . . . , p(p
n
−1
− 1). Поэтому f
(p
n
)
= p
n
− 1 −
− (p
n
−1
− 1) = p
n
− б) Числа m и n взаимно простые, поэтому существуют целые числа u и v, для которых um + vn = 1 (эти числа можно найти с помощью алгоритма Евклида. Пусть a и b — некоторые остатки отделения на m и n, те и 0 6 b 6 n − 1. Сопоставим

Глава 31. Элементы теории чисел паре (a, b) число c, которое является остатком отделения числа на mn. Ясно, что c≡avn≡a (mod m) и c≡bum≡b (mod Поэтому, в частности, разным парам (a, b) сопоставляются разные числа c. Мы получили взаимно однозначное отображение остатков отделения на m и n на остатки отделения на mn. При этом
НОД(c, m) = НОД(a(1 − um) + bum, m) = НОД(a, m) и НОД(c, n) =
= НОД(b, n). Поэтому числа c и mn взаимно простые тогда и только тогда, когда числа a и m взаимно простые и числа b и n тоже взаимно простые.
З а меча ни е. Используя задачи аи б, легко получить формулу для f
(n), где n
= p
a
1 1
. . . p
a
k
k
. Другое доказательство этой формулы приведено в решении задачи 14.36.
31.8. Пусть a
1
, a
2
, . . . , a
f
(n)
— все числа от 1 до n − 1, которые взаимно просты с n. Сопоставим числу остаток отделения числа на n. Число взаимно просто с n, поэтому мы снова получим одно из чисел a
1
, a
2
, . . . , a
f
(n)
. При этом число a(a
i
− при i 6= j не может делиться на n. Значит, мы получаем некоторую перестановку чисел a
1
, a
2
, . . . , a
f
(n)
. Поэтому. . . a
f
(n)
≡ a
1
. . . a
f
(n)
(mod Умножение на число b = a
1
. . . тоже задаёт некоторую перестановку чисел a
1
, a
2
, . . . , a
f
(n)
. Поэтому bb ≡ 1 (mod n) для некоторого числа b = a
i
. Умножив обе части сравнения (1) на получим требуемое. Согласно теореме Эйлера (задача 31.8) можно положить. Первое решение. Рассмотрим дроби 1/n, 2/n,
3/n, . . . , n/n; их количество равно n. Заменим каждую из этих дробей на соответствующую несократимую дробь. При этом получатся дроби, знаменателями которых являются делители числа n,
причём количество дробей со знаменателем d равно Второе решение. Запишем разложение числа n на простые множители n=p
a
1 1
p
a
2 2
. . . p
a
k
k
. Любой делитель d числа n имеет вид d = p
b
1 1
p
b
2 2
. . . p
b
k
k
, где 0 6
b
i
6
a
i
, i = 1, . . . , k. Поэтому в силу свойства мультипликативности функции Эйлера (задача 31.7 б (1 +
f
(p
1
)
+ . . . +
f
(p
a
1 1
)) . . . (1
+
f
(p
k
)
+ . . . Действительно, в правой части после раскрытия скобок мы получаем сумму всех слагаемых вида f
(p
b
1 1
) . . .
f
(p
b
k
k
)
=
f
(p
b
1 1
. . . p
b
k
k
).

Решения задач
413
Остаётся заметить, что +
f
(p)
+ . . . +
f
(p
a
)
= 1 + (p − 1) + (p
2
− p) + . . . + (p
a
− p
a
−1
)
= p
a
31.11. а) Ответ. Числа 171 и 52 взаимно простые, поэтому. Далее 24. Поэтому 2147
≡ 15 24·89+11
≡ 15 11
≡ 7 (mod б) Ответ. Числа 126 и 138 не взаимно простые их
НОД равен 6. Мы воспользуемся тем, что если a ≡ b (mod 23), то ≡ 6b (mod 138). Пусть a = 21 · 126 1019
. Тогда a ≡ 21 · 11 22·46+7
≡
≡ −2 · 11 7
≡ 9 (mod 23). Поэтому 126 1020
= 6a ≡ 54 (mod 138).
31.12. Согласно теореме Эйлера a
f
(m)
≡ 1 (mod m). Поделим f
(m) нас остатком kq + r, где 0 6 r < k. Тогда 1 ≡ a
f
(m)
≡
≡ (a
k
)
q
a
r
≡ a
r
(mod m). Следовательно, r
= 0, поскольку иначе мы получили бы противоречие с минимальностью числа k.
31.13. Числа a и a
n
− 1 взаимно простые. Поэтому согласно теореме Эйлера a
f
(a
n
−1)
≡ 1 (mod a
n
− 1). Из этого следует, что число f
(a
n
− 1) делится на n см. задачу 31.20).
31.14. Согласно теореме Эйлера x
p
a
i −1
i
(p
i
−1)
≡ 1 (mod p
a
i
i
). Воз- ведём обе части этого равенства в степень это число целое, поскольку L(n) делится на p
a
i
−1
i
(p
i
− 1)). В результате получим. Следовательно, число x
L(n)
− 1 делится на 1
, . . . , p
a
k
k
, поэтому оно делится на n.
31.15. а) Предположим, что число p простое и p > 2 (для p = требуемое утверждение очевидно. Пусть a — одно из чисел 1, 2,
3, . . . , p−1. Для него существует единственное число a, для которого aa ≡ 1 (mod p) см. решение задачи 4.63). Если a = то a
2
− 1 = (a − 1)(a + 1) делится на p, поэтому a = 1 или p − Таким образом, числа 2, 3, . . . , p − 2 разбиваются на пары, произведения которых дают остаток 1 при делении на p. Значит 1)! ≡ p − 1 ≡ −1 (mod Предположим теперь, что p = qr, где 1 < r, q < p. Тогда (p − делится на q, поэтому (p − 1)! 6≡ −1 (mod б) Предположим, что p = qr, где 1 < r < q < p. Тогда (p − делится на qr = p. Остаётся рассмотреть случай, когда p = q
2
, где — простое число. Если q
= 2, то q
2
= 4 и (3!)
2
= 36 делится на Если же q > 2, то (p − 1)! делится на q и на 2q, поэтому даже само число (p − 1)!, а не только его квадрат, делится на q
2
= p.
31.16. Если число n простое, то согласно теореме Вильсона
(задача 31.15 аи, поэтому f(n) = n. Если же число n составное, то, как следует из решения задачи 31.15 б

Глава 31. Элементы теории чисел 1)!)
2
≡ 0 (mod n) и 2(n − 1)! ≡ 0 (mod n). Поэтому a(n) = и b(n) = 1, значит, f(n) = 2.
31.17. Число a−b делится на n
1
, n
2
, . . . , n
k
, поэтому оно делится и на наименьшее общее кратное этих чисел. Применим индукцию по r. Предположим, что Будем искать целое число t так, чтобы для числа x
r
+1
= x
r
+ выполнялось сравнение x
n
r
+1
≡ a (mod p
r
+1
). Ясно, что (x
r
+ tp
r
)
n
= x
n
r
+ nx
n
−1
r
tp
r
+
n(n
− 1)
2
x
n
−2
r
t
2
p
2r
+ . . . =
= a + mp
r
+ nx
n
−1
r
tp
r
+ . . Здесь многоточием обозначены члены, делящиеся на p
r
+1
. Таким образом, нужно выбрать t так, чтобы число mp
r
+ делилось нате. число m + nx
n
−1
r
t делилось на p. По условию числа n и a не делятся на p. Поэтому число тоже не делится на p. В таком случае для любого числа m можно выбрать число так, что nx
n
−1
r
t
≡ −m (mod p).
31.19. По условию a = b + mp
n
, где m — целое число. Поэтому b
p
+ pb
p
−1
mp
n
+
p(p
− 1)
2
b
p
−2
(mp
n
)
2
+ . . Все слагаемые pb
p
−1
mp
n
,
p(p
− 1)
2
b
p
−2
(mp
n
)
2
, . . . делятся на p
n
+1
31.20. Запишем k в виде k = pn + r, где 0 6 r < n. Ясно, что 1 (mod a
n
− 1), поэтому a
k
≡ a
r
(mod a
n
− 1). Но если r > 0, то 6 a
r
6
a
n
−1
<
a
n
− 1. Поэтому a
r
≡ 1 (mod a
n
− 1) тогда и только тогда, когда r = 0, те. число k делится на n.
31.21. Применим индукцию по n. При n = 1 утверждение верно.
Действительно, если не все коэффициенты многочлена f(x) делятся на p, то cf(x) ≡ x
m
+ a
1
x
m
−1
+ . . . + a
m
(mod p) для некоторого целого числа c; здесь m < p. Поэтому согласно теореме Лагранжа
(задача 31.33) сравнение cf(x) ≡ 0 (mod p) имеет место не более чем для m различных по модулю p значений x. Поскольку m < p,
найдётся x, для которого f(x) 6≡ 0 (mod Предположим, что требуемое утверждение доказано для некоторого. Рассмотрим тождественное сравнение f(x
1
, . . . , x
n
, x
n
+1
)
≡
≡ 0 (mod p), у которого степень по каждой переменной меньше Запишем f(x
1
, . . . , x
n
, x
n
+1
) в виде, . . . , x
n
)x
m
n
+1
+ g
m
−1
(x
1
, . . . , x
n
)x
m
−1
n
+1
+ . . . + g
0
(x
1
, . . . , Для фиксированных x
1
, . . . , положим a
m
= g
m
(x
1
, . . . , x
n
), . . .
. . . , a
0
= g
0
(x
1
, . . . , x
n
). Сравнение a
m
x
m
n
+1
+ . . . + a
0
≡ 0 (mod p) выполняется для всех целых x
n
+1
, поэтому a
0
≡ . . . ≡ a
m
≡ 0 (mod p).

Решения задач
415
Таким образом, g
i
(x
1
, . . . , x
n
)
≡0 (mod p) для всех целых x
1
, . . . , Поэтому по предположению индукции все коэффициенты многочлена) делятся на p.