Учебное пособие Москва Издательство мцнмо 2007 удк 512. 1517. 1511. 1 Ббк 22. 14122. 161 П70 Прасолов В. В
 Скачать 3.28 Mb.
|
|
31.3. Докажите, что существует бесконечно много простых чисел вида 4k + 1. 31.4. а) Пусть p — простое число. Докажите, что если — простой делитель числа 2 p − 1, то q − 1 делится наб) Приведите пример простого числа p, для которого число непростое. Псевдопростые числа Согласно малой теореме Ферма для любого простого p число 2 делится на p. Натуральное число n > 1 называют псевдо- простым, если 2 n − 2 делится на n. 31.5. Докажите, что число 341 = 11 · 31 является псевдо- простым. Докажите, что если n — псевдопростое число, то число 2 n − 1 тоже псевдопростое. З а меча ни е. Существуют и чётные псевдопростые числа. Например, число 161 038 псевдопростое. Глава 31. Элементы теории чисел. Функция Эйлера Функция Эйлера) равна количеству тех из чисел 1, 2, . . . . . . , n − 1, которые взаимно просты с n. Например, если p — простое число, то f (p) = p − 1. 31.7. а) Докажите, что если p — простое число, то f (p n ) = = p n − б) Докажите, что если числа m и n взаимно простые, то f (mn) = f (m) f (n). 31.8. Докажите, что если число a взаимно просто сто) теорема Эйлера. Числа a и n взаимно простые. Докажите, что для некоторого натурального числа m число a m −1 делится на n. 31.10. Докажите, что n = P f (d), где суммирование вед тся по всем числам d, делящим n. 31.11. а) Найдите остаток отделения наб) Найдите остаток отделения на 138. 31.12. Пусть a и m — взаимно простые числа, k — наименьшее натуральное число, для которого a k ≡ 1 (mod Докажите, что f (m) делится на k. 31.13. Пусть a > 2 и n — натуральные числа. Докажите, что f (a n − 1) делится на Пусть n = p a 1 1 p a 2 2 . . . p a k k — разложение натурального числа n на простые множители. Назовём обобщённой функцией Эйлера функцию L(n), которая равна 1 при n=1 и НОК(p a 1 −1 1 (p 1 −1), . . . . . . , p a k −1 k (p k − 1)) при n > 1. 31.14. Докажите, что если числа x и n взаимно простые, то x L(n) ≡ 1 (mod n). 31.4. Теорема Вильсона. а) Докажите, что (p − 1)! + 1 делится на p тогда и только тогда, когда число p простое (теорема Вильсона). б) Докажите, что 1)!) 2 ≡ ( 0 (mod если p составное (mod если p простое Условия задач. Пусть a(n) и b(n) — остатки отделения чисел и ((n на n. Докажите, что f(n) = na(n) + + 2b(n) — простое число, причём любое простое число можно представить в таком виде. Задачи о сравнениях. Докажите, что если выполняются сравнения a ≡ ≡ b (mod n 1 ), . . . , a ≡ b (mod n k ), то a ≡ b (mod n), где n = = НОК(n 1 , . . . , n n ). 31.18. Пусть p — простое число, n и a — натуральные числа, не делящиеся на p. Докажите, что если сравнение a (mod p) имеет решение, то сравнение x n ≡ a (mod имеет решение для любого натурального r. 31.19. Докажите, что если a ≡ b (mod p n ), где p — простое число, то a p ≡ b p (mod p n+1 ). 31.20. Пусть a > 2 и n — натуральные числа. Докажите, что a k ≡ 1 (mod a n − 1) тогда и только тогда, когда k делится на n. * * * 31.21. Пусть p — простое число, f(x 1 , . . . , x n ) — многочлен с целыми коэффициентами, степень которого по каждой переменной меньше p. Докажите, что если для всех целых x 1 , . . ., выполняется сравнение f(x 1 , . . . , x n ) ≡ ≡ 0 (mod p), то все коэффициенты многочлена f(x 1 , . . . , делятся на p. 31.22. Пусть p — простое число, f(x 1 , . . . , x n ) — многочлен с целыми коэффициентами, для которого сравнение, . . . , x n ) ≡ 0 (mod p) выполняется для всех целых x 1 , . . . . . . , x n . Заменим в каждом мономе этого многочлена где m > p, на x r i , где r — остаток отделения на p. Докажите, что в результате получится тождественное сравнение ≡ 0 (mod p). 31.23. Пусть f(x 1 , . . . , x n ) — многочлен с целыми коэффициентами и со свободным членом, равным нулю. До Глава 31. Элементы теории чисел кажите, что если степень этого многочлена меньше n, то сравнение f(x 1 , . . . , x n ) ≡ 0 (mod p), где p — простое число, имеет решение, отличное от (0, 0, . . . , 0) (Шевалле). 31.24. Пусть a, b, c — целые числа. Докажите, что сравнение) имеет решение (x, y, z) 6= 6= (0, 0, 0) для любого простого числа p. 31.6. Функция. Делители Пусть d 1 , d 2 , . . . — различные делители числа n, включая 1 и Функция s k (n) определяется как сумма d k 1 + d k 2 + . . . В частности) — количество делителей числа n, s 1 (n) — сумма делителей числа n. Обычно используется обозначение s (n) = s 1 (n). 31.25. а) Докажите, что если p — простое число, то s k (p a ) = 1 + p k + p 2k + . . . + б) Докажите, что если числа m и n взаимно простые, то Число n называют совершенным, если s (n) = 2n, те. сумма всех делителей числа n, отличных от n, равна самому числу n. 31.26. а) Докажите, что если число 2 p − 1 простое, то число 2 p −1 (2 p − 1) совершенное (Евклид). б) Докажите, что если n — чётное совершенное число, то существует простое число вида 2 p − 1, для которого 2 p −1 (2 p − 1) Эйлер. Докажите, что если n — нечётное число, у которого есть ровно два разных простых делителя, то s (n) < 2n. 31.28. Докажите, что натуральное число n можно выбрать так, что отношение s (n)/n будет сколь угодно велико. а) Приведите пример чисел m 6= n, для которых б) Докажите, что если m 6= n, тов) Приведите пример чисел m 6= n, для которых n s (n) = = m s (m). Условия задач. Докажите, что Функция Мёбиуса определяется следующим образом: m (n) = 8 > < > : 1 при n = при n = p 1 . . . при n = p 2 m. 31.31. Докажите, что если F(n) = P d | n f(d), то n m (d)F(n/d) = X d | где сумма берётся по всем делителям d числа n (Мёбиус). 31.32. Докажите, что если F(n) = Q d | n f(d), то n F(n/d) m (d) = Y d | n F(d) m (n/d) 31.7. Квадратичные вычеты. Пусть p — простое число, f(x) = x n + a 1 x n −1 + . . . . . . + a n — многочлен с целыми коэффициентами. Докажите, что существует не более n различных целых чисел x i , для которых 0 6 x i 6 p − 1 и f(x i ) делится на p (Лагранж). Целое число a называют квадратичным вычетом по модулю если a ≡ b 2 (mod p) для некоторого целого числа b. В противном случае число a называют квадратичным невычетом. 31.34. Пусть p > 2 — простое число. Докажите, что среди чисел 1, 2, . . ., p − 1 ровно половина квадратичных вычетов и ровно половина квадратичных невычетов по модулю p. 31.35. Пусть 1 6 a 6 p − 1, где p > 2 — простое число. Докажите, что число a является квадратичным вычетом по модулю p тогда и только тогда, когда a (p −1)/2 ≡ 1 (mod Эйлер Глава 31. Элементы теории чисел. Пусть p > 2 — простое число. Докажите, что число является квадратичным вычетом по модулю p тогда и только тогда, когда p ≡ 1 (mod 4). 31.37. Пусть r — это 2 или нечётное число, p 1 , . . . , различные простые числа вида 4k + 1. Предположим, что −1 для всех i 6= j. Докажите, что уравнение x 2 − dy 2 = = −1, где d = p 1 . . . p r , имеет решение в целых числах. Квадратичный закон взаимности Для простого числа p символ Лежандра “ a p ” определяется следующим образом: “ a p ” = 8 > < > : 0, если a делится на если a — квадратичный вычет; −1, если a — квадратичный невычет. Символ Лежандра мы иногда будем обозначать Согласно задаче 31.35, если p — нечётное простое число, то a (p −1)/2 (mod p). Следовательно, (ab/p) = (a/p)(b/p) и “ −1 p ” = ( 1 при p = 4k + 1; −1 при p = 4k + Квадратичный закон взаимности заключается в следующем. Пусть p и q — различные нечётные простые числа. Тогда (−1) p−1 2 · q−1 Кроме того, если p — нечётное простое число, то Впервые квадратичный закон взаимности был доказан Гауссом. Сейчас известно много разных доказательств квадратичного закона взаимности. Как правило, они используют какие-то интерпретации символа Лежандра. Мы приведём две такие интерпретации, принадлежащие Гауссу (задача 31.38) и Золотарёву (задача 31.39). 31.38. Пусть p — нечётное простое число, а q — натуральное число, не делящееся на p. Для каждого натураль- Условия задач 405 ного числа l от 1 до 1 запишем lq ≡ ±r l (mod p), где 6 r l 6 p − 1 2 . Пусть m — количество всех встречающихся здесь минусов. Докажите, что Гаусс. Пусть p — нечётное простое число, a — число, взаимно простое си перестановка остатков отделения на p. Докажите, что тогда sgn p a,p =(a/p), где sgn = 1 для чётной перестановки и sgn = −1 для нечётной перестановки ( Золотарёв). 31.40. Докажите квадратичный закон взаимности с помощью леммы Гаусса (задача 31.38) и тождества из задачи. а) Докажите квадратичный закон взаимности с помощью задачи б) Пусть m — нечётное простое число. Докажите, что (−1) (m 2 −1)/8 31.42. Докажите квадратичный закон взаимности с помощью леммы Гаусса и тождества из задачи 11.31 ( Эйзен- штейн). * * * 31.43. Пусть p — простое число. Докажите, что для p = 12k ± 1 и −1 для p = 12k ± 5. 31.44. Пусть p — простое число. Докажите, что для p = 6k + 1 и −1 для p = 6k − 1. 31.45. Докажите, что существует бесконечно много простых чисел вида 6k + 1. 31.46. а) Пусть p = 2 n − 1 — простое число, причём p > Докажите, чтоб) Пусть p = 2 n + 1 — простое число, причём p > 3. Докажите, что −1. 31.47. Докажите, что 3 n −1 не делится на 2 n −1 при n>1. Глава 31. Элементы теории чисел. Гауссовы суммы Пусть p — нечётное простое число e 2 p i/p = cos(2 p /p) + + i sin(2 p /p). Для каждого целого числа a можно рассмотреть гауссову сумму g a = p −1 P k =1 “ k p ” e ak , где символ Лежандра. Ясно, что зависит только от остатка отделения на p и от самого числа p). 31.48. Докажите, что g 0 = 0. 31.49. Докажите, что g 2 1 = −1 p p. 31.50. Докажите, что cos 2 p 5 − cos 4 p 5 = √ 5 2 , sin 2 p 7 + sin 4 p 7 − sin 6 p 7 = √ 7 2 31.51. Докажите, что+ 1) p = −1. 31.52. Для каждого натурального n 6 p − 2 пара (n, n + имеет один из четырёх видов (R, R), (N, N), (N, R), (R, где R означает вычета невычет. Пусть RR, NN, NR, RN — количество всех пар соответствующего вида. а) Докажите, чтоб) Пусть e = (−1) (p −1)/2 . Докажите, что+ RN = 1 2 (p − 2 − e ), RR + NR = 1 2 (p − 1) − 1, NR + NN = 1 2 (p − 2 + e ), RN + NN = 1 2 (p − в) Докажите, что+ 4 4 , RN = p 4 − e 4 , NN = NR = p 4 + e − 2 4 31.10. Суммы двух квадратов Здесь мы доказываем, что любое простое число p = 4k + 1 можно представить в виде суммы квадратов двух целых чисел. Различные подходы приведены в задачах 31.53––31.55. Другие Условия задач 407 доказательства этого утверждения можно найти в решении задачи аи нас. Представление простого числа p = 4k + 1 в виде суммы двух квадратов единственно (задача Напомним, что простое число p = 4k + 3 нельзя представить в виде суммы двух квадратов (задача 4.45 а. Кроме того, произведение двух чисел, представимых в виде суммы двух квадратов, само представимо в виде суммы двух квадратов задача. Пусть p = 4k + 1 — простое число. а) Докажите, что существует целое число x, для которого+ 1 делится наб) Докажите, что можно выбрать целые числа 0 6 r 1 , r 2 < < √ p итак, что числа r 1 x + и r 2 x + будут давать одинаковые остатки при делении на p, причём (r 1 , s 1 ) 6= (r 2 , в) Докажите, что p = (r 1 − r 2 ) 2 + (s 1 − s 2 ) 2 31.54. Докажите, что любое простое число p = 4k + 1 можно представить в виде суммы квадратов двух целых чисел, воспользовавшись задачей 17.12. 31.55. Пусть p = 4k + 1 — простое число. а) Докажите, что уравнение x 2 + y 2 = mp имеет решение в натуральных числах x, y, б) Докажите, что если m > 1, то можно построить решение с меньшим m. 31.56. Докажите, что представление простого числа p = = 4k + 1 в виде суммы двух квадратов целых чисел единственно. (Мы не различаем представления p = x 2 + y 2 , отличающиеся только перестановкой x и y или заменами знака и y.) 31.11. Суммы четырёх квадратов. Докажите, что если каждое из чисел a и b является суммой четырёх квадратов целых чисел, то их произведение тоже является суммой четырёх квадратов целых чисел Глава 31. Элементы теории чисел. Пусть p — нечётное простое число. Докажите, что существуют целые числа x, y и m, для которых 1 + x 2 + y 2 = = mp, причём 0 < m < p. 31.59. Пусть p — нечётное простое число. а) Докажите, что можно выбрать натуральное число и целые числа x 1 , x 2 , итак, чтоб) Докажите, что наименьшее такое m нечётно. в) Докажите, что наименьшее такое m равно 1. 31.60. Докажите, что любое натуральное число можно представить в виде суммы четырёх квадратов целых чисел ( Лагранж). 31.12. Первообразные корни по простому модулю Пусть p — простое число, x — натуральное число, не превосходящее. Тогда согласно малой теореме Ферма x p −1 ≡ 1 (mod Наименьшее натуральное число d, для которого x d ≡ 1 (mod p), называют показателем, которому принадлежит x по модулю Число x называют первообразным корнем по модулю p, если его показатель равен p −1. Эквивалентное условие состоит в том, что числа x, x 2 , . . . , дают разные остатки при делении на Первообразные корни существуют для любого простого числа задача 31.63). 31.61. Докажите, что показатель d делит число p − 1. |