Учебное пособие Москва Издательство мцнмо 2007 удк 512. 1517. 1511. 1 Ббк 22. 14122. 161 П70 Прасолов В. В
 Скачать 3.28 Mb.
|
|
31.22. Согласно малой теореме Ферма x p i ≡ x i (mod p), поэтому. Значит, после указанных замен мы получим многочлен g(x 1 , . . . , x n ), степень которого по каждой переменной строго меньше p, причём g(x 1 , . . . , x n ) ≡ 0 (mod p) для всех целых, . . . , x n . Согласно задаче 31.21 все коэффициенты многочлена, . . . , x n ) делятся на p. 31.23. Предположим, что сравнение f(x 1 , . . . , x n ) ≡ 0 (mod имеет только решение (0, . . . , 0). Тогда сравнение − (f(x 1 , . . . , x n )) p −1 ≡ (1 − x p −1 1 ) . . . (1 − x p −1 n ) (mod выполняется тождественно. При (x 1 , . . . , x n ) = (0, . . . , 0) это очевидно, а при (x 1 , . . . , x n ) 6= (0, . . . , 0) это следует из малой теоремы Ферма. Применим к обеим частям сравнения (1) замены, описанные в условии задачи 31.22. С одной стороны, согласно этой задаче в результате мы должны получить тождественное сравнение. С другой стороны, в правой части вообще никаких замен не делается, поэтому в правой части после замен стоит многочлен, моном высшей степени которого равен ±x p −1 1 . . . x p −1 n . В левой же части первоначально стоит многочлен степени меньше n(p − 1); после указанных замен его степень может только уменьшиться. Получено противоречие. Это утверждение очевидным образом следует из теоремы Шевалле (задача 31.23), поскольку степень рассматриваемого многочлена строго меньше числа его переменных. а) Делителями числа являются числа 1, p, p 2 , . . . , б) Пусть d и d ′ — делители чисел m и n. Тогда dd ′ — делитель числа mn. Для взаимно простых чисел m и n верно и обратное: любой делитель числа mn однозначно представляется в виде произведения делителей чисел m и n. Поэтому если и s k (n) = P b k j , то s k (mn) = P a k i b k j = `P a k i ´`P b k j ´ = s k (m) s k (n). 31.26. а) Числа и (2 p − 1) взаимно простые, поэтому согласно задаче 31.25 б 1)) = s (2 p −1 ) s (2 p − 1). Далее, согласно задаче 31.25 аи б) Пусть n = 2 p −1 m, где m нечётно, — чётное совершенное число. Тогда 2 p m = 2n = s (n) = s (2 p −1 ) s (m) = (2 p − 1) s (m). Поэтому делится на 2 p −1. Пусть m=(2 p −1)m ′ . Тогда 2 p (2 p −1)m ′ = 2 p m = = s (n) = s (2 p −1 ) s (m) = (2 p − 1) s (m), поэтому s (m) = 2 p m ′ . Из Глава 31. Элементы теории чисел равенства следует, что m+m ′ = 2 p m ′ = s (m). С другой стороны, оба числа m и являются делителями числа m. Поэтому равенство m + m ′ = s (m) может выполняться лишь в том случае, когда число m простое и m ′ = 1. 31.27. Пусть n = p a 1 1 p a 2 2 , где и p 2 — простые числа, причём p 1 > 3 и p 2 > 5. Тогда из неравенства s (n) = p a 1 +1 1 − 1 p 1 − 1 · p a 2 +1 2 − 1 p 2 − 1 < p a 1 +1 1 p 1 − 1 · p a 2 +1 2 p 2 − 1 = n p 1 p 1 − 1 · p 2 p 2 − следует, что s (n) n < p 1 p 1 − 1 · p 2 p 2 − 1 6 3 2 · 5 4 = 15 8 < 2. 31.28. Число s (n)/n является суммой всех чисел вида d/n, где — делитель числа n. Но d/n = d ′ , где d ′ — некоторый делитель числа n, причём когда d пробегает все делители числа n, тоже пробегает все делители числа n. Значит, где сумма берётся по всем делителям числа Положим n = N!. Тогда s (n) n > 1 + 1 2 + 1 3 + 1 4 + . . . поскольку числа 1, 2, 3, . . . , N являются делителями числа n. Оста- ётся заметить, что гармонический ряд расходится (задача 30.6). 31.29. а) Ответ и б) Пусть n = p a 1 1 . . . и p 1 > p 2 > . . . > p k . Тогда и наибольшее простое число, на которое делится n f (n), равно. При этом максимальная степень числа p 1 , на которую делится n f (n), равна 2a 1 − 1. Таким образом, если известно число, то известны числа и a 1 . Пусть n = p a 1 1 n 2 . Тогда 1 (p 1 − 1) , поэтому известны числа и и т. д. в) Ответ и 14. 31.30. Ясно, что h 2n + 2 k i − h 2n k i = 0, если числа 2n + 1 и 2n + не делятся на k. В противном случае эта разность равна 1. Следо- Решения задач 417 вательно, n +2 X k =1 h 2n + 2 k i − n X k =1 h 2n k i = s 0 (2n + 1) + s 0 (2n + 2) + Поэтому если f(n) = 2n P k =1 s 0 (k) − n P k =1 h 2n k i , то f(n + 1) − f(n) = 1. Ясно также, что f(1) = 1. 31.31. Прежде всего проверим, что при всех n > 1 выполняется соотношение n m (d) = 0. Пусть n = p a 1 1 . . . p a k k . Тогда n m (d) = X d | p 1 ...p k m (d) = 1 − C 1 k + C 2 k + . . . + (−1) k = (1 − 1) k = Ясно, что Пусть n/d 1 = m. Тогда m m (b) = ( 1 при n = d 1 ; 0 при n 6= Поэтому n „ f(d 1 ) X d 2 b =n/d 1 m (b) « = f(n). 31.32. Непосредственно сводится к задаче 31.31 с помощью логарифмирования. Применим индукцию по n. При n = 1 утверждение очевидно. Пусть числа f(x 1 ) и f(x) делятся на p (x — целое число). Тогда число f(x) − f(x 1 ) = x n − x n 1 + a 1 (x n −1 − x n −1 1 ) + a n −1 (x − x 1 ) = =(x−x 1 )g(x) делится на p. При этом g(x) =x n −1 +b 1 x n −2 +. . многочлен с целыми коэффициентами, зависящими только от, . . . , и x. Если 0 6 x 6 p − 1 и x 6= x 1 , тоне делится на p. Поэтому на p должно делиться число g(x), и мы можем воспользоваться предположением индукции. Сопоставим каждому целому числу x, где 1 6 x 6 p − остаток отделения на p числа x 2 . Числами сопоставляется одно и тоже число, причём x 6= p − x. Кроме того, согласно теореме Лагранжа (задача 31.33) сравнение x 2 ≡ c (mod p) не может иметь Глава 31. Элементы теории чисел больше двух решений. Поэтому образ рассматриваемого отображения состоит из (p − 1)/2 элементов. А этот образ как рази состоит из квадратичных вычетов. Если a≡b 2 (mod p), то согласно малой теореме Ферма задача. Поэтому любой квадратичный вычет является решением уравнения x (p −1)/2 ≡ 1 (mod p). Согласно теореме Лагранжа (задача 31.33) количество решений этого сравнения не превосходит (p−1)/2, а согласно задаче 31.34 количество квадратичных вычетов равно (p −1)/2. Поэтому квадратичные вычеты это в точности решения сравнения x (p −1)/2 ≡ 1 (mod Если a — квадратичный невычет, то a (p −1)/2 ≡ −1 (mod p). Действительно, сравнение x 2 ≡ 1 (mod p) имеет только два решения ±1 (mod p), а мы знаем, что (a (p −1)/2 ) 2 = a p −1 ≡ 1 (mod p). 31.36. Воспользуемся критерием Эйлера (задача 31.35). Если, то (−1) (p −1)/2 = (−1) 2k = 1, а если p = 4k + 3, то (−1) 2k+1 = −1. 31.37. Предположим, что уравнение x 2 − dy 2 = −1 не имеет решений в целых числах. Пусть ( x , h ) — фундаментальное решение уравнения Пелля x 2 − dy 2 = 1. Число d тоже имеет вид + 1, поэтому x 2 ≡ ( h 2 + 1) (mod 4). Квадрат нечётного числа при делении на 4 даёт остаток 1, поэтому x нечётно, а h чёт- но. Равенство 1)( x + 1) 4d = h 2 показывает, что h 2 /4 (квадрат целого числа) можно представить в виде произведения двух квадратов целых чисел u 2 = x − 1 и v 2 = x + 1 2d 2 , где и d 2 — делители числа d. Натуральные числа u и v взаимно простые, потому что НОД( x − 1, x + 1) = 2. Кроме того, u 6= 0, поскольку x 6= 1. Далее d 1 u 2 = 1 2 ( x + 1) − 1 2 ( x − 1) = Предположим, что d 1 6= 1 и d 2 6= 1. По условию r = 2 или нечётно, поэтому или d 2 — произведение нечётного числа простых чисел. С луча й 1. d 1 — произведение нечётного числа простых чи- сел. Пусть p — произвольный простой делитель числа d 2 . Тогда. . . “ p i 2k+1 p ” = (−1) 2k+1 = Но это противоречит тому, что d 1 u 2 ≡ −1 (mod p), поскольку является квадратичным вычетом по модулю Случай произведение нечётного числа простых чисел Решения задач 419 Снова для произвольного простого делителя p числа получаем. Но это противоречит тому, что d 2 v 2 ≡ 1 (mod Полученные противоречия показывают, что либо d 1 = 1 и d 2 = либо d 1 = d и d 2 = Случай и d 2 = d, те Это противоречит предположению о том, что уравнение x 2 − − dy 2 = −1 не имеет решений. С луча й 2. d 1 = d и d 2 = 1, те Таким образом, (v, u) — решение уравнения Пелля x 2 − dy 2 = С другой стороны, u 2 v 2 = x 2 − 1 4d = h 2 4 , поэтому uv = h 2 , а значит < h . Но это противоречит тому, что было выбрано фундаментальное решение. Прежде всего заметим, что если l и k — различные натуральные числа от 1 до 1 2 , то r l 6= r k . Действительно, если r l = то (l ± k)q делится на p, поэтому l± k делится на p. Но |l± k| 6 p − Таким образом, набор чисел r 1 , r 2 , . . . , совпадает с набором. Поэтому, перемножив сравнения ±r 1 (mod p), . . . , p − 1 2 q ≡ ±r (p −1)/2 (mod получим 1 2 ” ! q p−1 2 ≡ (−1) m r 1 . . . r (p −1)/2 = (−1) m “ p − 1 2 ” ! (mod Следовательно, q p−1 2 ≡ (−1) m (mod p). Но q p−1 2 ≡ “ q p ” (mod p) задача. Рассмотрим многочлен A(x 1 , . . . , x p ) = Q 16i<j6p (x i − Под действием чётной перестановки многочлен A не изменяется, а под действием нечётной перестановки он изменяет знак. Поэтому знак любой перестановки равен отношению A(x s (1) , . . . , к A(x 1 , . . . , x p ). Положим x 1 = 1, . . . , x p = p. Тогда sgn p a,p = Y 16i<j6p p a,p (i) − p a,p (j) i − j ≡ Y 16i<j6p ai − aj i − j = = Y 16i<j6p a ≡ a p(p −1)/2 (mod Поскольку a p ≡a (mod p), получаем sgn p a,p ≡a (p −1)/2 ≡(a/p) (mod p). Глава 31. Элементы теории чисел. Пусть lq ≡ e l r l (mod p), где e l = ±1 и 1 6 r l 6 p − 1 2 . Докажем, что e l = (−1) [2lq/p] . Действительно 1 тогда и только тогда, когда {lq/p} < 1/2. С другой стороны, для любого положительного число [2 a ] = [2[ a ] + 2{ a } ] = 2[ a ] + [2{ a } ] чётно тогда и только тогда, когда { a } < 1/2. Полагая a = {lq/p}, получаем, что число чётно тогда и только тогда, когда {lq/p} < 1/2. Итак, лемму Гаусса можно записать следующим образом (−1) m , где m = (p −1)/2 P l =1 [2lq/p]. Для любого нечётного числа a число a + p чётно, поэтому + p)/2 p ” = “ (a + p)/2 p ” = где + p)l p i = (p −1)/2 X l =1 h al p i + (p −1)/2 X l =1 l = (p −1)/2 X l =1 h al p i + p 2 − 1 В частности, при a = 1 получаем (−1) (p 2 −1)/8 . Подставив это выражение в (1), после сокращения получим (−1) M , где M = (p −1)/2 P l =1 h al p i Пусть p и q — различные нечётные простые числа. Тогда (−1) (p−1)/2 P l=1 [ql/p]+ (q−1)/2 P l=1 [ pl/q] Остаётся заметить, что 1 2 · q − 1 согласно задаче 5.29. 31.41. а) Пусть P = {0, 1, . . . , pq − 1} и P = {(a, b): 0 6 a < p, 0 6 6 b < q}. Согласно китайской теореме об остатках отображение c = (c (mod p), c (mod q)) является взаимно однозначным отображением на Рассмотрим отображения m , n : P → P, заданные формулами m (a, b) =a+pb и n (a, b) =qa+b. Ясно, что m (a, b) =(a, a+pb (mod q)), Решения задач 421 поэтому отображение переставляет элементы вида (a 0 , b), где a 0 фиксировано. Следовательно перестановка множества и sgn m = “ p q ” p = “ p q ” . Аналогично sgn Рассмотрим теперь на множестве P перестановку n −1 m : qa+b7→ 7→ a + pb. Знак этой перестановки равен (−1) k , где k — количество пар элементов множества P, для которых выполняются неравенства+ и a + pb < a ′ + pb ′ . По условию |b − b ′ | < и |a − a ′ | < p, поэтому приходим к следующим неравенствами. Таким образом, k = C 2 q C 2 p = p − 1 2 · q − 1 2 . В итоге получаем sgn m sgn n = sgn n −1 m = (−1) p−1 2 · q−1 б) При m = 3 требуемое равенство легко проверяется. Предположим, что m > 3 — нечётное натуральное число, для которого выполняется требуемое равенство. Тогда + 2 ” = “ −1 m + 2 ”“ m m + 2 ” = (−1) m+1 2 ( −1) m−1 2 · m+1 2 “ m + 2 m ” = = (−1) m+1 2 “ 2 m ” = (−1) m+1 2 ( −1) m2 −1 8 = (−1) (m+2)2−1 8 |