Учебное пособие Москва Издательство мцнмо 2007 удк 512. 1517. 1511. 1 Ббк 22. 14122. 161 П70 Прасолов В. В
 Скачать 3.28 Mb.
|
|
31.61. Пусть p − 1 = qd + r, где 0 6 r < d. Тогда 1 ≡ x p −1 ≡ x qd +r ≡ ≡ x r (mod p). Но d — это наименьшее натуральное число, для которого. Следовательно, r = 0. Глава 31. Элементы теории чисел. Решение аналогично решению задачи 31.61. 31.63. а) Пусть остаток x принадлежит показателю d. Тогда остатков 1, x, x 2 , x 3 , . . . , различны и все они удовлетворяют уравнению X d ≡ 1 (mod p). Поэтому никаких других остатков, удовлетворяющих этому уравнению степени d, нет (задача Любой остаток y, принадлежащий показателю d, удовлетворяет уравнению y d ≡ 1 (mod p). Следовательно, y — это один из остатков. Но принадлежит показателю d тогда и только тогда, когда числа d и k взаимно просты. Действительно, остатки x k , x 2k , . . . , неравны тогда и только тогда, когда числа k, 2k, . . . , (d − 1)k не делятся на Мы доказали, что если показателю d принадлежит хотя бы один остаток, то ему принадлежит ровно f (d) остатков. б) Каждый остаток x принадлежит некоторому показателю делящему p − 1. Согласно задаче а) показателю d принадлежит не более f (d) остатков. Поэтому p − 1 6 P f (d), где суммирование ведётся по всем числам d, делящим p − 1. При этом если хотя бы одному показателю d, делящему p − 1, принадлежит менее f (d) остатков, то неравенство строгое p − 1 < P f (d). С другой стороны, согласно задаче 31.10 p − 1 = P f (d). Поэтому каждому показателю d, делящему p − 1, принадлежит ровно f (d) ос- татков. в) Непосредственно следует из задачи б достаточно положить p − 1. 31.64. а) Предположим сначала, что n = p 2 q. Пусть x = pq. Тогда 0 (mod n), но x d +1 ≡ 0 (mod n) для любого натурального числа Предположим теперь, что n = p 1 . . . p k , где p 1 , . . . , p k — попарно различные простые числа. Тогда если число x d +1 − x делится на p 1 , . . . , p k , то оно делится и на n. Если число p простое, то согласно малой теореме Ферма x p −1 ≡ 1 (mod p), поэтому x (mod p). Значит, x d +1 ≡ x (mod p) для любого числа делящегося на p − 1. Таким образом, в качестве d можно взять НОК(p 1 − 1, . . . , p k − б) В задаче а) доказано, что если d = НОК(p 1 − 1, . . . , p k − то x d +1 ≡ x (mod n) для всех x. Остаётся доказать, что если x d +1 ≡ ≡ x (mod n) для всех x, то d делится на НОК(p 1 − 1, . . . , p k − Для этого достаточно доказать, что d делится на каждое из чисел 1, . . ., p k − Если x d +1 ≡ x (mod n), то x d +1 ≡ x (mod p i ). Пусть x i — первообразный корень по модулю p i . В таком случае x r i ≡ 1 (mod p i ) тогда и только тогда, когда r делится на p i − 1. Если x d +1 i ≡ x i (mod p i ), Решения задач 429 то x d i ≡ x d +p i −1 i ≡ x d +1+(p i −2) i ≡ x i · x p i −2 i ≡ x p i −1 i ≡ 1 (mod Поэтому d делится на p i − 1 (задача 31.62). 31.65. а) Пусть q — нечётный простой делитель числа a p − Тогда a p ≡ 1 (mod q). Поэтому согласно задаче 31.62 показатель числа a по модулю q является делителем числа p, те или p. Если d = 1, то a ≡ 1 (mod q), поэтому q — делитель числа. Если d=p, то согласно задаче 31.61 p — делитель числа Учитывая, что число q − 1 чётно, получаем q − 1 = б) Пусть q — нечётный простой делитель числа a p + 1. Тогда −1 (mod q). Поэтому a 2p ≡ 1 (mod q). Следовательно, показатель числа a по модулю q является делителем числа 2p. Ясно, что a 6≡ 1 (mod q) и a p 6≡ 1 (mod q), поэтому d = 2 или d = 2p. Если 1 (mod q), тот. е. q — делитель числа a + Если d = 2p, то 2p — делитель числа q − 1. Поэтому q − 1 = 2px. 31.66. Прежде всего заметим, что такие простые числа есть: согласно задаче 31.65 а) все простые делители числа 2 p − 1 имеют такой вид. Предположим, что существует лишь конечное число простых чисел вида 2px + 1, а именно, числа p 1 , . . . , p n . Рассмотрим число (p 1 . . . p n ) p − 1. Согласно задаче 31.65 а) это число имеет простой делитель вида 2px + 1. Действительно, пусть a = p 1 . . . Тогда a ≡ 1 (mod p), те. Число 1 p 2 x = 1 + p − 1 2 px + (p − 1)(p − 2) 3! p 2 x 2 + . . взаимно просто с px = a − 1, поэтому у числа a p − 1 должны быть делители, отличные от a − 1. Ясно также, что число (p 1 . . . p n ) p − взаимно просто с p 1 , . . . , p n . Мы получили простое число вида, отличное от p 1 , . . . , p n , что противоречит предположению. Пусть q — простой делитель числа 2 2 n + 1. Тогда 2 2 n ≡ ≡ −1 (mod q), поэтому 2 2 n+1 ≡ 1 (mod q). Согласно задаче показатель d числа 2 по модулю q является делителем числа Следовательно, d=2 n +1 , поскольку 2 2 n 6≡1 (mod q). Таким образом, число является делителем числа q − 1 (задача 31.61). 31.68. При n > 1 числа 3 и p взаимно простые. Согласно задаче б −1, поэтому 3 2 n−1 ≡ −1 (mod 2 n + 1). Показатель числа 3 по модулю 2 n + 1 является делителем числа 2 n , причём он больше 2 n −1 . Следовательно, показатель числа 3 по модулю 2 n + равен 2 n Глава 31. Элементы теории чисел. Если n делится на p − 1, то a n ≡ 1 (mod p) для любого взаимно простого с p. Значит, S ≡ p − 1 ≡ −1 (mod Предположим теперь, что n не делится на p − 1. Пусть x — первообразный корень по модулю p. Тогда согласно задаче 31.62 x n 6≡1 (mod p). Число x взаимно просто с p, поэтому набор остатков при делении на p чисел x, 2x, 3x, . . . , (p − 1)x совпадает с набором, 2, . . . , p − 1. Следовательно, S ≡ x n S (mod p). Учитывая, что 1 (mod p), получаем S ≡ 0 (mod p). 31.70. Заметим, что если r > 1, то (1 + km r ) m ≡ 1 (mod Действительно, (1 + km r ) m = 1 + C 1 m km r + C 2 m k 2 m 2r + . . . В этой сумме слагаемое C 1 m km r = делится на m r +1 . Последующие слагаемые делятся на m 2r , поэтому они тоже делятся на m r +1 . Таким образом, и т. д. Если x — первообразный корень по модулю p a , тоне существует натурального s<p a −1 (p −1), для которого x s ≡1 (mod Предположим, что x t ≡ 1 (mod p) для некоторого натурального < p − 1. Тогда согласно задаче 31.70 x tp a −1 ≡ 1 (mod p a ). Получено противоречие, поэтому x — первообразный корень по модулю. Пусть k — наименьшее натуральное число, для которого 1 (mod p a ). Тогда p a −1 (p − 1) делится на k задача 31.12). Ясно, что x k ≡ 1 (mod p), поэтому k делится на p − 1. Таким образом p b (p − 1), где 0 6 b 6 a − 1. Предположим, что b 6 a − 2. Тогда, возведя обе части сравнения x p b (p −1) ≡1 (mod p a ) в степень получим x p a −2 (p −1) ≡1 (mod p a ), что противоречит условию. Следовательно, те. Предположим, что числа x и x + p не являются первообразными корнями по модулю p 2 . Оба эти числа являются первообразными корнями по модулю p, поэтому согласно задаче) и (x + p) p −1 ≡ 1 (mod p 2 ). Следовательно, число (x + p) p −1 −x p −1 = (p −1)x p −2 p + C 2 p −1 x p −3 p 2 + . . . делится на а значит, p(p − делится нате делится на Но это противоречит тому, что p − 1 и x взаимно просты с p. 31.74. Числа x и p взаимно простые, поэтому согласно малой теореме Фермате. Наименьшее натуральное, для которого x k ≡ 1 (mod p 2 ), равно p(p − 1), поэтому не делится на p. Возведём равенство x p −1 = 1 + pt в степень n = p a −2 , где В результате получим (1 + pt) n = 1 + npt + C 2 n p 2 t 2 + . . . + C n n p n t n Решения задач 431 Согласно задаче 14.33 делится на p a при s > 2. С другой стороны, npt=p a −1 t не делится на p a . Поэтому x p a −2 (p −1) ≡1+npt6≡ 6≡ 1 (mod p a ). Значит, согласно задаче 31.72 число x — первообразный корень по модулю p a 31.75. Ясно, что f (2p a ) = f (p a ). Пусть x — первообразный корень по модулю p a . Заменив при необходимости x на x + можно считать, что число x нечётно. Достаточно доказать, что 1 (mod p a ) тогда и только тогда, когда x k ≡ 1 (mod 2p a ). Если 1 (mod p a ) и x k ≡ 1 (mod 2), то x k ≡ 1 (mod 2p a ). Утверждение в обратную сторону очевидно. Числа 1 и 3 являются первообразными корнями по модулями. Остаётся доказать, что если n > 3, то первообразного корня по модулю не существует. Поскольку f (2 n ) = 2 n −1 , достаточно доказать, что x 2 n−2 ≡ 1 (mod 2 n ) при n > 3 для любого нечёт- ного x. Пусть x = 1 + 2t. Тогда x 2 = 1 + 4t(t + 1) ≡ 1 (mod 8). При 3 требуемое утверждение доказано. Предположим теперь, что 1 + 2 n t, где n > 3. Тогда x 2 n−1 = (1 + 2 n t) 2 = 1 + 2 n +1 t + 2 2n t 2 ≡ ≡ 1 (mod 2 n +1 ). 31.77. Предположим, что x — число, взаимно простое с Согласно задаче 31.14 x L(m) ≡ 1 (mod m), где L(m) — обобщённая функция Эйлера. Поэтому достаточно доказать, что если число не имеет указанного в условии задачи вида, то L(m) Если число m имеет два различных нечётных простых делителя и p 2 , то числа p 1 − 1 и p 2 − 1 имеют нетривиальный общий делитель. Поэтому НОК(p 1 − 1, p 2 − 1) < (p 1 − 1)(p 2 − 1), а значит) Если m = 2 a p b , где a > 2, b > 1 и p — нечётное простое число, то f (m) = 2 a −1 p b −1 (p − 1) и L(m) = НОК(2 a −1 , p b −1 (p − 1)). Числа 2 a −1 и p − 1 имеют общий делитель 2, поэтому L(m) < f (m). 31.78. Для каждого натурального числа n можно выбрать натуральное число k так, что 2 2k−2 < n 6 2 2k . Тогда p (n)/n 6 p (2 2k )/n < p (2 2k )/2 2k−2 = 4 p (2 2k )/2 Поэтому достаточно доказать, что lim k →∞ p (2 2k )/2 2k = Каждое простое число p, удовлетворяющее неравенствам 2 m −1 < < p6 2 m , является делителем биномиального коэффициента C 2 m−1 2 m = = (2 m )! ((2 m −1 )!) 2 , поэтому 2 m > C 2 m−1 2 m > Y 2 m−1 < p62 m p > (2 m −1 ) p (2 m ) − p (2 m−1 ) Глава 31. Элементы теории чисел Следовательно, p (2 m ) − p (2 m −1 ) 6 2 m m − Просуммируем неравенства (2) для m = k + 1, k + 2, . . . , 2k и воспользуемся тем, что в этом случаете В результате получим p (2 2k ) − p (2 k ) 6 2 k +1 + 2 k +2 + . . . + 2 2k k 6 Ясно также, что p (2 k ) 6 2 k . Поэтому p (2 2k ) 2 2k 6 2 k 2 2k + 2 2k+1 k2 2k = 1 2 k + 2 k 31.79. Согласно задаче 14.34, если делит C k n , то Поэтому C k n = Q p6n p m 6 n p (n) . Запишем такие неравенства для всех биномиальных коэффициентов с фиксированными сложим их. В результате получим (1 + 1) n = n X k =0 C k n 6 (n + те. Поэтому достаточно доказать, что если, тот. е. ln 2 − 2 3 > ln(n + При x > 2 производная функции ln(x + отрицательна, поэтому указанное неравенство достаточно проверить для n = 201. Это делается непосредственными вычислениями ln 2 − 2/3 ≈ и ln 202 201 ≈ 0,02641. 31.80. Каждое число p, удовлетворяющее неравенствам n < p 6 6 2n, является делителем биномиального коэффициента C n 2n , поэтому Прологарифмировав это неравенство, получаем p (2n) − p (n) < 2n ln 2 ln n (1) Решения задач 433 Предположим, что для некоторого n уже доказано неравенство p (n) < 3 ln 2 n ln n . Тогда из неравенства (1) следует, что p (2n) < 3 ln 2 n ln n + 2 ln 2 n ln n = 5 ln 2 n ln Мы хотим доказать неравенство p (2n) < 3 ln 2 2n ln(2n) . Для этого достаточно доказать неравенство ln 2 n ln n 6 3 ln 2 те Последнее неравенство переписывается в виде ln n > 5 ln 2. Оно выполняется при n > 2 Чтобы можно было применить индукцию, нужно ещё доказать неравенство p (2n + 1) < 3 ln 2 2n + 1 ln(2n + Заметим, что из (1) и очевидного неравенства p (2n + 1) 6 p (2n) + следует, что p (2n + 1) < p (n) + 2n ln 2 ln n + 1 < 3n ln 2 ln n + 2n ln 2 ln n + Таким образом, достаточно доказать неравенство ln 2 n ln n + 1 < 3 ln 2 2n + 1 ln(2n + те+ Ясно, что 3 2n + 1 n > 6, поэтому достаточно доказать неравенство + ln n n ln 2 < 6 ln n ln(2n + Если n > 55, то выражение в правой части больше 5,1053, а выражение в левой части меньше 5,1052 (монотонность обоих выражений доказывается дифференцированием). Чтобы завершить доказательство, нужно непосредственно проверить, что утверждение верно для всех n от 55 до 109. После этого можно воспользоваться тем, что если утверждение верно для некоторого n, то оно верно для 2n и 2n + 1. ГЛАВА МНОГОЧЛЕНЫ — Основная теорема алгебры заключается в том, что любой многочлен имеет по крайней мере один (комплексный) корень. Из этого с помощью теоремы Безу (задача 10.2) легко выводится, что многочлен степени n имеет ровно n корней, с учётом их кратности. У основной теоремы алгебры есть много разных доказательств. Одно из возможных использует следующую теорему Руше, которая имеет и самостоятельный интерес. Пусть f и g — многочлены и g — замкнутая несамо- пересекающаяся кривая на комплексной плоскости. Докажите, что если) − g(z)| < |f(z)| + при всех z ∈ g , то внутри кривой расположено одинаковое количество корней многочленов f и g, с учётом их кратности ( Руше). |