Сборник материалов выездных школ команды Москвы на Всероссийскую математическую олимпиаду
 Скачать 3.42 Mb.
|
|
− 2 = py? 11. а) Если число p = 12k ± 1 простое, то 3 (p−1)/2 ≡ 1 mod б) Если число p = 12k ± 5 простое, тов) Для каких простых чисел p разрешимо в целых числах уравнение x 2 − 3 = py? 12. Обозначим p := ( +1, если a — квадратичный вычет по модулю p, −1, если a — квадратичный невычет по модулю Например (по задаче 10; ab p = a p b по задаче 7. а) Критерий Эйлера. a p−1 2 ≡ a p mod б p = (−1) (p−1)/2 P x=1 2ax в p = (−1) (p−1)/2 P x=1 ax для нечетного a. г)* Квадратичный закон взаимности Гаусса p = (−1) p−1 2 · q−1 2 p для простых нечетных чисел p и д) Как при помощи предыдущих задач быстро вычислять Зачетные задачи 2 а, в, ж б, в б, в б, в б, в а, б 11 а. Из них письменно 4 в 9 а). Контрольные вопросы. Может ли −1 быть квадратичным вычетом по какому-нибудь простому модулю а) Может; б) не может Квадратичные вычеты. Какие из следующих сравнений разрешимы: а) x 2 ≡ 10 (б) x 2 ≡ 2 (в) x 2 ≡ 6 (17)? III. Какие из следующих утверждений верны для любых целых a и m, таких что 0 < a < а) Сравнение x 2 ≡ a mod m имеет не более 2 решений. б) Сравнение ax ≡ 1 mod m имеет не более 1 решения. в) Сравнение ax ≡ 1 mod m имеет не менее 1 решения. Указания и решения. а) Ответ квадраты целых чисел дают остатки отделения на 3: 0, на 4: 0, на 5: 0, 1, на 6: 0, 1, 3, на 7: 0, 1, 2, на 8: 0, 1, на 9: 0, 1, 4, на 10: 0, 1, 4, 5, 6, Решение. Достаточно найти квадраты остатков. Заметим, что 0 и 1 квадраты по любому модулю. Кроме того, числа и (имеют один остаток отделения на n, поэтому можно смотреть только остатки чисел для 2 6 k 6 n/2. 2 2 ≡ 0 mod 4; 2 2 ≡ 4 mod 5; 2 2 ≡ 4, 3 2 ≡ 3 mod 6; 2 2 ≡ 4, 3 2 ≡ 2 mod 7; 2 2 ≡ 4, 3 2 ≡ 1, 4 2 ≡ 0 mod 8; 2 2 ≡ 4, 3 2 ≡ 0, 4 2 ≡ 7 mod 9; 2 2 ≡ 4, 3 2 ≡ 9, 4 2 ≡ 6, 5 2 ≡ 5 mod б) По пункту а) число имеет остаток 0 или 1 отделения на Поэтому если хотя бы одно из чисел a или b не делится на 3, то число a 2 + не делится на Также по пункту а) число может иметь остаток отделения на семь 0, 1, 2 или 4. Ни одно из чисел 0 + 1, 0 + 2, 0 + 4, 1 + 1, 1 + 2, 1 + 4, 2 + 2, 2 + 4, 4 + 4 не делится на 7. Откуда получаем требуемое. в) По пункту а) число имеет остаток отделения на четыре или 1. Значит, сумма двух квадратов может иметь остаток 0, 1 или Что и требовалось доказать. д) Приведем доказательство Дона Загира (в исполнении МВ. Пра- солова, ср. [1]) того, что простые числа вида 4k + 1 представимы в виде суммы двух квадратов Гл. 3. Миникурс по теории чисел Рассмотрим число способов представить простое число p = 4k + в виде p = x 2 + 4yz, где x, y, z — натуральные числа. Достаточно показать, что это число способов нечетно. Действительно, пусть мы это доказали. Все способы, в которых y 6= очевидным образом разбиваются на пары тройке (x, y, z) сопоставляется тройка (x, z, y). Если общее число способов нечетно, то число способов, в которых y = z, также нечетно. Значит, число p можно представить в виде p = x 2 + (Чтобы доказать, что общее число способов нечетно, разделим все способы, кроме одного, на пары. Для этого рассмотрим следующую фигуру, состоящую из квадрата со стороной x и четырех прямоугольников размера y × z (рис. 1). Возьмем на плоскости квадрат со стороной x с вершинами (0, 0), (0, x), (x, и (x, 0). Приставим к нему прямоугольник y × z с вершинами в (x, x), (x, x + y), (x − z, x + y) и (x − z, x). Три оставшихся прямоугольника y × × z получаются изданного поворотом на 90 ◦ , и относительно центра квадрата yyy yy yy yy yy yy yy yy yy yy yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy y zzzzzzzzzz zzzzz zzzzz zzzzzz zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz z x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x Рис. Каждую такую фигуру можно разрезать на квадрат и четыре прямоугольника двумя способами. Для этого нужно продолжить стороны прямоугольников, как показано на рисунках рис. 1 ирис x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x Рис. 2 Квадратичные вычеты 91 Проверим, что таким образом мы разобьем все способы представления, кроме одного, на пары. Разберем два случая, показанных на рисунках 1 и Случай 1: x + y < z или 2z < x. Мы имеем два способа разрезания нашей фигуры. В первом участвуют квадрат со стороной x и четыре прямоугольника y × z, а во втором — большой квадрат со стороной x + 2y и четыре прямоугольника (z − x − y) × y. Так каждому представлению, в котором x + y < z, мы сопоставляем представление. И наоборот, каждому представлению, в котором 2z < x, мы сопоставляем представление, в котором x + y < Тем самым все способы представления, в которых x + y < z или 2z < оказались разбиты на пары. Случай 2: x < z < x + y или z < x < 2z. Каждому представлению p = x 2 + 4yz, в котором x < z < x + y, мы сопоставляем представление p = (2z − x) 2 + 4(x + y − z)z, и наоборот. Тем самым все представления, в которых x < z < x + y или z < x < 2z, также оказались разбиты на пары. Проверим, что ровно один способ представления не охватывается этими двумя случаями. Разберем все варианты. Пусть сначала x < z. Если при этом x + y < < z, то мы имеем ситуацию на рис. 1, слева. Если x + y > z, то мы имеем ситуацию на рис. 2, слева. Если x + y = z, то из рисунка видно, что число p — квадрат целого числа, что противоречит простоте числа p. Пусть теперь x > z. Если x < 2z или x > 2z, то мы имеем ситуацию на рисунке или 2. Если x = 2z, то число p > 2 четное, что опять же противоречит простоте числа Осталось разобрать случай x = z. Тогда x|p, значит, x = 1. Это соответствует представлению p = 1 2 + 4 · k · 1. Это и есть способ без пары. е) Первое решение. Рассмотрим целое число n > 3. Три последовательных числа n 2 + 1, n 2 + 2, n 2 + 3 меньше числа (n + 1) 2 . Но для любого натурального a, a 2 или (n + 1) 2 6 a 2 . Значит, ни одно из рассмотренных чисел не является точным квадратом. Второе решение. По пункту а) ни одно из чисел 8k + 5, 8k + 6, 8k + не является точным квадратом. б) Ответ {(3k − 1, 15k 2 − 6k)} = {(3k + 2, 15k 2 + 24k + Указание к еж используйте малую теорему Ферма. а) Указание. Остатки отделения на p чисел 2 · 1, 2 · 2, . . . . . . , 2 · (4k + 2) совпадают с остатками отделения на p чисел a 1 , a 2 , . . . . . . , a 2k+1 , −a 2k+2 , −a 2k+3 , . . . , −a 4k+2 , где, a 2 , . . . , a 2k+1 , a 2k+2 , a 2k+3 . . . , a 4k+2 } = {1, 2, . . . , 4k + Поэтому 2 4k · (4k)! ≡ −(4k)! mod p. Гл. 3. Миникурс по теории чисел а, 10 а, баб б. Эти задачи решаются аналогично задаче. в) Ответ p = 8k ± 1. 11. в) Ответ p = 12k ± 1. 12. Указания. а) Обозначим через P произведение всех квадратичных вычетов по модулю p. Если a квадратичный невычет, то a p−1 сравнимо с произведением всех квадратичных невычетов по модулю По задаче 6 имеем P ≡ ±1 mod p. Поэтому и по теореме Вильсона последнее произведение сравнимо с −P . Значит, a p−1 2 ≡ −1 mod Второе решение. Пусть {a 1 , a 2 , . . . , a p−1 2 } — все квадратичные вычеты по модулю p. Пусть, напротив, a — квадратичный невычет и a p−1 2 ≡ 1 mod p. Тогда многочлен x p−1 2 − 1 имеет более p − 1 корней. Противоречие стем, что многочлен степени n над Z p имеет не более n корней. в) a p = 2 p a + p 2 p 8 а, 9 а, 10 а, б. Указание (СВ. Конягин). Пусть z = (1 + Тогда (z + 1/z) p − (z p + 1/z p ) представимо в виде p(A + B √ 2), где, B — целые числа а, б. Указание (СВ. Конягин). Пусть z = (1 + i √ 3)/2. Тогда + 1/z) p − (z p + 1/z p ) представимо в виде p(A + B √ 3), где A, B— целые числа. Литература [1] Прасолов В. В. Задачи по алгебре, арифметике и анализу. М.: МЦНМО, Первообразные корни (Это занятие мотивировано следующей общей проблемой решить сравнение a x ≡ b mod m (при заданных параметрах a, b, m). Будем считать, что a и b не делятся на m. 1. Сформулируйте и обоснуйте алгоритм решения такого сравнения для m = 2, 3, 4, 5, Пусть (g, m) = 1. Вычет g называется первообразным корнем по модулю, если остатки отделения на m чисел g 1 , g 2 , . . . , g ϕ(m) ≡ 1 различны Первообразные корни 2. Докажите существование первообразного корня по модулю а) б) в) p = 2 l + где+ ж) Здесь p — простое число. Теорема о первообразном корне. Для любого простого p существует число g, для которого остатки отделения на p чисел g 1 , g 2 , g 3 , . . . , g p−1 ≡ 1 различны. Леммы к теореме о первообразном корне. Пусть p простое и a не делится на а) p − 1 делится на наименьшее k > 0, для которого a k ≡ 1 mod Указание используйте малую теорему Ферма. б) Для любых целых n и a сравнение x n ≡ a mod p имеет не более n решений. в) Если p − 1 делится на d, то сравнение x d ≡ 1 mod p имеет ровно d решений. а) Если (a, 35) = 1, то a 12 ≡ 1 mod б) Если m делится на два различных простых нечетных числа и (a, m) = 1, то a ϕ(m) 2 ≡ 1 mod m. 5. а) Если m делится на два различных простых нечетных числа, то не существует первообразного корня по модулю б) Пусть x ≡ 3 mod 4. Может ли x 2 ≡ 1 mod 2 в При n > 2 не существует первообразного корня по модулю 2 n 6. а) Число 2 является первообразным корнем по модулю Указание 2 2 = 1 + б) Число 2 является первообразным корнем по модулю Указание 2 4 = 1 + 5 · в) Найдите первообразный корень по модулю 7 n 7. Пусть g первообразный корень по модулю простого p > а) Существуют такие t и u, что (g + pt) p−1 = 1 + pu и u не делится наб) Для любого целого положительного n существует первообразный корень по модулю p в) Тоже по модулю 2p n 8. Теорема. Первообразные корни существуют только по модулям, 4, p n , 2p n 9. Пусть p простое и a не делится на p. Положим ord a = ord p a := = min {k > 1 | a k ≡ 1 mod p}. Число ord p a называется порядком (или индексом) элемента a по модулю p. Гл. 3. Миникурс по теории чисел а) Если a m ≡ a n mod p, то m − n делится наб в) Если ord x и ord y взаимно просты, то ord(xy) = ord x · ord y. 10. При каких n а) 2 n − 1 делится наб делится на 3 в) 5 n − 1 делится наг делится на 2 100 ? 11. Найдите длину периода дроби а) 1/3 100 ; б) 1/7 100 12. а) При циклической перестановке цифр в периоде дроби 1/7 = = 0,(142857) получатся дроби вида 1/7, 2/7, 3/7, 4/7, 5/7, 6/7. Докажите аналогичный факт для дроби 1/p, если в ней длина периода равна p − б) Найдите множество остатков отделения чисел видана в) Докажите, что в десятичной записи дроби 1/3 встречается любая комбинация из 20 идущих подряд цифр. Найдите такие n, чтобы среди последних 1000 цифр числа 2 n нашлось 100 подряд идущих а) нулей; б) девяток. Аналогично задаче 13 вопрос про 5 n 15. Лемма Гензеля. Пусть p — простое число, x ≡ 1 mod p n , x 6≡ 1 mod p n+1 , p > 2 или n > 1. Докажите, что: а) если (a, p) = 1, то x a ≡ 1 mod p n , но x a 6≡ 1 mod p б) x p ≡ 1 mod p и если n > 1 либо p > 2, тов) если a = p k q и q взаимно просто сто и x a 6≡ 1 mod p n+k+1 16. Если x — первообразный корень по модулю p 3 , где p — нечетное простое, то x — первообразный корень по модулю p n 17. Если d|(2 2 n + 1), то 2 n+1 |(d − Контрольные вопросы. Найдите первообразный корень по модулю а) б) в) 3. II. Для любого ли числа m существует первообразный корень по модулю а) Для любого; б) не для любого. Пусть P (x) — многочлен с целыми коэффициентами. Назовем его корнем по модулю p любой элемент a множества {0, 1, 2, . . . , p − для которого p|P (a). Какие из следующих утверждений верны для любого простого p и любого целого n > 0? Первообразные корни 95 а) Многочлен x p−1 − 1 имеет ровно p − 1 корень по модулю б) Многочлен x n − 1 имеет ровно n корней по модулю в) Многочлен степени n имеет не более n корней по модулю Указания и решения. Указание. Пункт в) вытекает из того, что если первообразного корня нетто сравнение x 2 l−1 ≡ 1 mod p имеет p − 1 = 2 l > 2 l−1 решений. Остальные пункты аналогичны. б) Указание. Докажем более общее утверждение многочлен степени над Z p не может иметь более n корней в Z p . Здесь многочленом называется набор его коэффициентов по модулю p, а не функция. Пусть многочлен P (x) степени n имеет в Z p различные корни x 1 , . . . . . . , x n , x n+1 . Представьте его в виде (x) = b n (x − x 1 ) . . . (x − x n )+ + b n−1 (x − x 1 ) . . . (x − x n−1 ) + . . . + b 1 (x − x 1 ) + интерполяция Ньютона. Последовательно подставляя в сравнение (x) ≡ 0 mod p вычеты x 1 , . . . , x n , x n+1 , получим b 0 ≡ b 1 ≡ . . . ≡ b n−1 ≡ ≡ b n ≡ 0 mod Тоже самое решение можно записать итак. Пусть P — многочлен. Тогда многочлен P − P (a) делится нате) для некоторого многочлена Q с deg Q < deg P . Поэтому если P (a) = = 0, то P = (x − a) Q для некоторого многочлена Q степени меньше deg P . Теперь требуемое в задаче утверждение доказывается индукцией по степени многочлена P в) Указание. Заметьте, что многочлен x p−1 − 1 над Z p имеет ровно p − 1 корень и делится на x d − 1. Докажите, что если многочлен степени имеет ровно a корней и делится на многочлен степени b, то этот многочлен степени b имеет ровно b корней. Другое решение можно получить, заметив, что если p = kd, то для любого a сравнение y k ≡ a mod p имеет не более k решений. в) Ответ при 2 98 | Указание. По 11 а) для решения задачи достаточно доказать, что 5 2 k есть минимальная ненулевая степень пятерки, которая дает остаток при делении на 2 k+2 . Это вытекает из 11 аи сравнения 5 2 k ≡ ≡ 2 k+2 + 1 mod 2 k+3 . Докажем это сравнение индукцией по База k = 0 легко проверяется. Пусть сравнение верно для k. Тогда 2 k = = t · 2 k+2 + 1, где t нечетно. Поэтому 2 k+1 = (5 2 k ) 2 = t 2 · 2 2k+4 + t · 2 k+3 + 1 ≡ t · 2 k+3 + 1 ≡ 2 k+3 + 1 mod 2 k+4 Гл. 3. Миникурс по теории чисел Проверка простоты чисел Мерсенна (СВ. Конягин Здесь необходимо определение и простейшие свойства сравнений по модулю (см. раздел Малая теорема Ферма. Решите задачи 2 д) и 6 а) оттуда, а также 11 а) из раздела Первообразные корни. Малая теорема Ферма не является достаточным условием про- стоты. а) Докажите, что если число p > 5 простое, то число n = (2 2p − составное, но 2 n−1 ≡ 1 mod б) Найдите такое составное n, что при (a, n) = 1 выполнено a n−1 ≡ 1 mod n. 2. Докажите, что а) если n > 2 — простое число и a не делится на n, то a (n−1)/2 ≡ ±1 mod б) если n = 2 s k + 1 и a (n−1)/2 ≡ −1 mod n для некоторого a, то любой простой делитель p числа n удовлетворяет сравнению p ≡ 1 mod в) если n = 2 s k + 1, k 6 2 s и a (n−1)/2 ≡ −1 mod n для некоторого то n простое. Мы получили достаточное условие простоты чисел специального вида. Отметим, что если число n = 2 s k + 1 действительно является простым, то, как правило, найти число a, удовлетворяющее сравнению a (n−1)/2 ≡ −1 mod n, можно небольшим перебором. Цель оставшихся задач — доказательство следующего критерия простоты чисел 2 m − 1. В дальнейшем считаем, что m > Критерий Люка. Число n = 2 m − 1 простое тогда и только тогда, когда m простое и делится на n. Здесь последовательность Люка задана формулами M 1 = 4 и M k = M 2 k−1 − 2. 3. Докажите, что если число 2 m − 1 простое, то число m простое. Далее p, p > 5, — простое число. Обозначим x ± k = (2 + √ 3) k ± ± (2 − √ 3) k , X + = {k : x + k ≡ 0 mod p} и X − = {k : x − k / √ 3 ≡ 0 mod Решите задачи 10 и 11 из раздела Квадратичные вычеты при помощи указаний от СВ. Конягина.) Докажите, что а) для любого целого k числа x + k и x − k / √ 3 целые; б) если z 1 , z 2 ∈ X + , тов) если z 1 , z 2 ∈ X − , тог) если z 1 ∈ и z 2 ∈ X − , то z 1 + z 2 ∈ д) p + 1 ∈ или p − 1 ∈ X − ; Проверка простоты чисел Мерсенна 97 е) если X + 6= ∅ и z — минимальный положительный элемент множества, то X + = {(2k + 1)z}, где k пробегает множество целых чисел, и z < ж) если m простое, то M k = x + 2 k−1 5. Пусть m — простое число и n = 2 m − 1. Докажите, что а) если n простое, то M m−1 ≡ 0 mod б) если M m−1 ≡ 0 mod n, то n простое. Контрольные вопросы. Какие из указанных чисел могут быть простыми при некотором n > а) 2 n + б) 2 n − в) 3 · 2 n + где. Вычислите (2 + √ 3) 4 + (2 а) 97 + б) в) 194. III. Известно, что число 5 · 2 n+1 + 1 делит 2 5·2 n + 1. Что можно сказать о числе 5 · 2 n+1 + а) Оно простое; б) оно составное; в) оно может быть и простыми составным, в зависимости от числа Указания и решения. а) Действительно, 2 p = 2 · (2 2 ) p−1 2 ≡ 2 mod 3. Поэтому n = = (2 p − 1) 2 p + 1 3 составное. Далее, 2 2p = 2 2 · (2 p−1 ) 2 ≡ 4 mod p. Значит, 2 2p − 4 делится на Так как p > 3, то n − 1 = (2 2p − 4)/3 также делится на 2p. Следовательно (2 2p ) n−1 2p ≡ 1 mod (2 2p − 1). Итак, 2 n−1 − 1 делится наб) Указание. Можно искать n в виде n = pqr, где p, q, r — различные простые числа. а) Действительно n−1 − 1 = (a n−1 2 ) 2 − 1 = (a n−1 2 − 1)(a n−1 2 + делится на n по малой теореме Ферма. Поэтому одно из чисел a n−1 2 − 1, a n−1 2 + 1 делится наб) Пусть 2 t — наибольшая степень двойки, делящая ord p a (см. определение в задаче 9 раздела Первообразные корни. Тогда ord p a = 2 t где l нечетно. По задаче 9 а) пункта Первообразные корни p − 1 делится на ord p a = 2 t l. Поэтому достаточно доказать, что t > s. Гл. 3. Миникурс по теории чисел По задаче 9 а) раздела Первообразные корни n − 1 = 2 s k делится на ord p a = 2 t l. Значит, k делится на l. Если t < s, то (n − 1)/2 = 2 s−1 k делится на 2 t l. Отсюда a n−1 2 ≡ 1 mod p, что противоречит a n−1 2 ≡ −1 mod в) Если n составное, то у него имеется простой делитель p 6 √ n. По предыдущему пункту p > 2 s + 1, откуда n > (2 s + 1) 2 . Это противоречит тому, что n = 2 s k + 1 6 (2 s ) 2 + 1. 5. а) 2 + √ 3 = ((1 +Алгоритм Евклида для гауссовых чисел (А. Я. Канель-Белов Всем хорошо знаком алгоритм Евклида. Даны два числа a, b. Из них выбирается большее, из большего вычитается меньшее, и большее заменяется на разность, с новой парой чисел производится та же процедура. С помощью алгоритма Евклида доказываются арифметические свойства чисел, и это вы изучали раньше. Приведем принципиально новые (для большинства школьников) его применения. В этом разделе используется понятие комплексных чисел. Решите уравнения в целых числах. а) x 2 + 4 = б) x 2 + 2 = y в x 3 + y 3 = Попробуйте порешать их, не читая дальнейшего Впрочем, у вас вряд ли получится. Возвращайтесь к этой задаче по мере чтения дальнейшего материала. При решении уравнения x 2 + 4 = в целых числах хочется действовать так x 2 + 4 = (x + 2i)(x − 2i), а дальше при нечетном x оба эти множители взаимно просты, и потому оба кубы. Из этого вытягивается решение. (Случай четного x хитрее обе скобки могут делиться на + i) 3 .) Попробуйте довести решение, а затем сравнить с приведенным в конце темы. Одним словом, хочется наслаждаться дополнительными возможностями при разложении на множители за счет использования гауссовых чисел, те. чисел вида a + bi с целыми a и b. Однако не все коту масленица так получается не всегда, но иногда все же получается. Чтобы применять разложение на множители для решения уравнений, нужна однозначность разложения на простые множители. Если она имеет место, то мы имеем все те же арифметические удовольствия, что и для целых чисел. Следующая задача показывает удивительный факт для арифметических удовольствий достаточно доказать геометрический факто возможности деления с остатком Алгоритм Евклида для гауссовых чисел 2. Будем называть простыми те гауссовы числа, которые не раскладываются на (отличные от ±1 и ±i) множители. а) Однозначность разложения на простые множители вытекает из следующего свойства (аналога основной леммы арифметики). Факториальность. Если простое число p делит ab, то p делит a или p делит б) Факториальность вытекает из следующего свойства. Главноидеальность. Пусть d есть наибольший общий делитель чисел a, b (дайте его определение самостоятельно. Тогда ma + nb = d для некоторых чисел m, в) Главноидеальность обеспечивается возможностью делить с остатком (причем остаток должен быть меньше делителя. То есть она вытекает из следующего свойства. Евклидовость. Для любых чисел a, b существует такое число что |a − kb| < Про обычные числа и многочлены вы все знаете. Докажем евкли- довость множества целых гауссовых чисел. Покажем, как разделить a на b. Множество чисел (p + qi)b, кратных b, образуют квадратную решетку со стороной |b|. Число a попадает в один из образовавшихся квадратиков. Остается воспользоваться геометрическим фактом расстояние от точки внутри квадрата до ближайшей вершины строго меньше длины стороны квадрата. Верна ли евклидовость (и, значит, факториальность!) в множестве чисел вида a + bξ, где ξ есть а) √ −2? б) √ −3? в) (1 г) (1 д) (1 − √ −7)/2? 4. Эту задачу проще решать без гауссовых чисел, однако потренируйтесь их применять! а) Докажите что простое число вида 4k − 1 не разлагается в сумму двух квадратов, а простое вида 4k + 1 разлагается одним способом. б) Докажите, что существует число, ровно 1024 способами разлагающееся в сумму двух квадратов. Дополнение Следующие две задачи посвящены алгоритму Евклида для вещественных чисел, те. цепным дробям. От прямоугольника отрезают квадрат и с оставшимся прямоугольником производят туже процедуру. Может ли последовательность Гл. 3. Миникурс по теории чисел отношений сторону этих прямоугольников быть периодической, если одна из сторон исходного прямоугольника равна 1, а другая равна а) √ 2; б) (1 + √ 5)/2; в) 3 √ 2; г)* √ 2005? 6*. Пусть α — иррациональное число. Применим к паре (α, 1) алгоритм Евклида. Докажите что получившиеся числа будут величинами наилучших приближений (по недостатку или по избытку) αn к целым. Число αn называется наилучшим приближением, если при всех 6 m < n расстояние от αn до ближайшего целого меньше расстояния до ближайшего целого. Аналогично определяются наилучшие приближения по недостатку и по избытку. Зачетные задачи 1 б 2 а)–в); 3 ага, б). Указания и решения. а) Ответ. x = ±2, y = 2 и x = ±11, y = Решение (Р. А. Девятов). Перейдем к целым гауссовыми получим уравнение (x + 2i)(x − 2i) = Целое гауссово число называется точным кубом, если оно равно для некоторого целого гауссова b. Заметим, что обратимые числа ±1, ±i все являются точными кубами. Поэтому точным кубом является любое целое гауссово число, представимое в виде ωa 3 , где a — целое гауссово число и ω — одно из обратимых чисел ±1, ±i. Поэтому мы будем называть точными кубами числа такого вида. Два целых гауссовых числа a и b называются ассоциированными, если a = ωb, где ω — одно из обратимых чисел ±1, Лемма. Оба числа x + 2i и x − 2i являются точными кубами. Доказательство. Будем использовать единственность разложения на простые гауссовы множители с точностью до умножения на обратимые числа ±1, ±i. Пусть d = НОД (x + 2i, x − 2i). Тогда x + 2i − − (x − 2i) = 4i = −i(1 + делится на d. Так как число 1 + i простое, то d — степень числа 1 + i, причем не более чем четвертая. Заметим, что разложение на простые целые гауссовы для числа x − 2i отличается от разложения x + 2i заменой всех простых множителей на сопряженные. Так как 1 + i = i(1 − i), то степени, в которых 1 + i входит в разложение чисел x + 2i и x − 2i на множители, одинаковы. Обозначим их через k. Тогда делится на 1 + i во вдвое большей степени 2k. Так как делится на 3, то и k делится на 3. Так как d — степень (1 + i), причем не более чем четвертая, то x + 2i либо не делится на 1 + i, либо делится на (1 + i) 3 Разные задачи по элементарной теории чисел 101 Если x + 2i не делится на 1 + i, то x + 2i и x − 2i взаимно просты. Так каких произведение (x + 2i)(x − 2i) является точным кубом, то сами числа x + 2i ив этом случае являются точными кубами. Если x + 2i = a(1 + для некоторого целого гауссова a, то и x − 2i = = b(1 + для некоторого целого гауссова b. Тогда y 3 = ab(1 + i) 6 , т. е. y 3 делится на (1 + i) 6 . Значит, y делится на (1 + i) 2 . Поэтому ab = = y (1 + i) 2 3 , те является точным кубом. Но a и b взаимно просты, поэтому сами являются точными кубами. А значит, и x + 2i = a(1 + и x − 2i = b(1 + являются точными кубами. Продолжение решения. Пусть x + 2i = (c + di) 3 = c 3 + 3c 2 di + 3cd 2 i 2 + d 3 i 3 = c 3 − 3cd 2 + (3c 2 d − Приравняем мнимые части 2 = 3c 2 d − d 3 , 2 = d(3c 2 − d 2 ). Это равенство обычных целых чисел, поэтому можно разобрать только 2 случая d = = ±2 и d = Случай 1. d = ±1. Тогда 3c 2 − 1 = ±2, те или 3. Но −1 оно равняться не может, значит, c = ±1, c + di = 1 + i или ассоциировано с ним, x + 2i = 2 + 2i или ассоциировано с ним, откуда x = ±2, y = Случай 2. d = ±2. Тогда 3c 2 − 2 = ±1, те или 3. Но 1 оно равняться не может, значит, c = ±1, c + di = 2 + i или ассоциировано с ним, x + 2i = 11 + 2i или ассоциировано с ним, откуда x = ±11, y = б) Используйте 3 а). в) Используйте 3 в. б) Если p не делит b, то тогда pm + bn = 1. Если при этом p делит ab, то тогда p делит nab + mpa, те делит в) Положим a ′ = a − kb. Любой общий делитель чисел a ′ , b является общим делителем чисел a, b. В тоже время множество чисел вида ma ′ + nb содержит a (и, разумеется, b), а значит, и любое число вида pa + qb. Аналогично можно убедиться в обратном — что множество чисел вида pa + qb содержит множество чисел вида ma ′ + nb. Итак, пару) можно заменить на пару (a ′ , b), которая в разумном смысле «меньше». Процесс останавливается на паре (s, 0), те. на нахождении наибольшего общего делителя. а) Аналогично задаче 1 г. Необходимый геометрический факт: любая точка внутри прямоугольника × 1 удалена на расстояние строго меньше 1 от ближайшей вершины. б) Факториальность неверна 4 = 2 · 2 = (1 + √ −3)(1 − √ −3). 1–3. См. книгу Постников ММ. Теорема Ферма введение в теорию алгебраических чисел. § 4. М Наука, 1978. 5, 6. См. книгу Арнольд В. И. Цепные дроби. М МЦНМО, 2000. Гл. 3. Миникурс по теории чисел Разные задачи по элементарной теории чисел Разные задачи (8–9). АИ. Галочкин 1. Дискретность множества целых чисел. Решите уравнения в целых положительных числах: а) 1 x + 1 y + 1 z = б) 4xy + 4yz + 4xz = 5xyz + в) y 3 = x 3 + 9x 2 + г) (x 2 + y 2 )(x + y − 3) = 2xy (в целых числах). д) Пусть x, y, z, u, v, w — такие целые положительные числа, что x + 1 y + 2003 z = u + 1 v +Найдите наибольшее возможное значение разности y − v. 2. Десятичная система счисления. Признаки делимости. а) В числе 65 432 789 вычеркните наименьшее число цифр так, чтобы оставшееся число делилось наб) Для того чтобы число делилось на 7, необходимо и достаточно, чтобы разность между числом с отброшенной последней цифрой и удвоенной последней цифрой делилась на в) Если число делится на 1998 и между любыми его цифрами вставить подряд три нуля, то вновь получившееся число тоже будет делиться наг) Число обратили в бесконечную десятичную дробь, вычеркнули первую цифру после запятой и получившееся число обратили в обыкновенную дробь. Какая дробь получилась? д) В последовательности [2 n √ 2] имеется бесконечное множество четных чисел. Теорема единственности разложения чисел в произведение простых сомножителей. Метод спуска. Решите в целых числах уравнения: а) 3 · 2 x + 1 = б) x 2 + y 2 + z 2 = в) x 2 + y 2 = г) x 4 + y 4 = z 2 4. Применение принципа Дирихле. а) Если (a, m) = 1, то разрешимо сравнение a x ≡ 1 mod б) Если p — простое число, то разрешимо сравнение 1 + x 2 + y 2 ≡ 0 mod p. Разные задачи по элементарной теории чисел 103 в) Разрешимо сравнение ax + by ≡ 0 mod m для некоторых |x|, |y| 6 6 √ m, |x| + |y| 6= г) Если m — нечетное число, не кратное пяти, то существует число, делящееся на m, десятичная запись которого состоит из одних единиц. Применение формула) Любое целое число можно представить в виде суммы кубов пяти целых чисел. б) Если m 2 + mn + делится на 35 2 , то m и n делятся на 35. 6. Целая часть числа. Решите уравнения а) x 2 = б) [x] + [3x] + [5x] = в) x 2 − 5[x] + 4 = Указания. в) Достаточно решить для взаимно простых x и z. Тогда y 2 = = (z − x)(z + x), где (z − x, z + x) ∈ {1, г) Используйте в. Ответ нет решений. Разные задачи (8–10). ДА. Пермяков, И. Н. Шнурников 1. Пусть p и q — различные простые числа. Сколько делителей у числа p n · q m ? 2. Найдите остаток отделения на 7. 3. Докажите, что число 2222 5555 + 5555 делится на 7. 4. а) Докажите, что 1 n + 2 n + . . . + (n − 1) n делится на n при нечетном б) Найдите все натуральные n > 1, такие что 1 n + 2 n + . . . + (n − 1) n делится на n. 5. Назовем натуральное число n удобным, если n 2 + 1 делится на 000 001. Докажите, что среди чисел 1, 2, . . . , 1 000 000 четное число удобных. Докажите, что 11 n+2 + 12 делится на 133 при любом натуральном. Найдите остаток отделения на 7 числа 10 + 10 100 + 10 1000 + . . . + 10 10 000 000 000 8. Пусть 56a = 65b. Докажите, что a + b — составное число. Докажите, что число является точным квадратом тогда и только тогда, когда у него нечетное число натуральных делителей. а) Пусть p > 5 — простое число. Докажите, что существует число вида 111 . . . 111, которое делится на p. Гл. 3. Миникурс по теории чисел б) Пусть n — натуральное число, взаимно простое с 10. Докажите, что существует число вида 111 . . . 111, которое делится на n. 11*. Пусть n — натуральное число, такое что n + 1 делится на Докажите, что сумма всех натуральных делителей n делится на 24. 12*. Докажите, что ни одно из чисел вида 10 нельзя представить в виде суммы двух кубов натуральных чисел. Докажите, что существует не менее 100 значений α таких что и sin α, и cos α рациональны. Для любого целого n число n P k=1 1 k нецелое. Покажите, что для любого натурального числа n существует бесконечно много пар взаимно простых чисел a, b, таких что a делит n + и b делит n + a 2 16. Докажите, что для каждого натурального числа n > 1 найдется кратное ему число m < n 4 , в десятичной записи которого используется не более 4 различных цифр. Найдите все натуральные числа n, для которых все n чисел, состоящие из n − 1 цифры 1 и одной цифры 7, простые. Решите уравнение 3 m + 4 n = 5 k в натуральных числах. Найдите все нечетные числа n > 1, для которых существует такая перестановка a 1 , a 2 , . . . , a чисел 1, 2, . . . , n, что все n следующих выражений положительны a 1 − a 2 + a 3 − . . . + a n , a 2 − a 3 + a 4 − . . . . . . − a n + a 1 , a 3 − a 4 + . . . + a n − a 1 + a 2 , . . . , a n − a 1 + a 2 − . . . . . . + a n−1 20. Существует ли множество из 2007 натуральных чисел, сумма любого подмножества которых есть квадрат, куб или большая степень целого числа. Докажите, что в любое конечное множество натуральных чисел можно добавить еще несколько чисел так, что каждое число из полученного набора будет делить сумму всех остальных чисел набора. Контрольные вопросы. Выберите все значения n из приведенных ниже, при которых+ 2 n + . . . + (n − 1) n делится на а) б) в) 10. II. Существует ли простое число вида 111 . . . 111, где количество единиц равно а) Существует; б) не существует Разные задачи по элементарной теории чисел 105 Разные задачи (10–11). И. Н. Шнурников, А. Засорин 1. Найдите все целые числа n, для которых а) n 2 + 1 делится наб. Докажите, что существует бесконечно много натуральных n, для которых число 4n 2 + 1 делится одновременно и на 13, и на 5. 3. Докажите, что для всех натуральных n имеем: а) 169|3 3n+3 − 26n − б) 19|2 2 6n+2 + в) F n |2 F n − 2, где F n = 2 2 n + г) 3 · (1 5 + 2 5 + 3 5 + . . . + n 5 ) делится над е) (2 n − 1) 2 |2 (2 n −1)n − 1. 4. Докажите, что а) 13|2 70 + 3 б) 11 · 31 · 61|20 15 − 1. 5. а) Докажите, что существует бесконечное число таких натуральных чисел n, чтоб) Найдите все такие простые числа n. 6. Докажите, что если k нечетное, а n натуральное, то 2 n+2 |k 2 n − 1. 7. Докажите, что для натуральных m и a > 1 имеем m −1 a −1 , a −1 = = (a − 1, m). 8. Исследовать, в зависимости от натурального числа n, какое из чисел a n = 2 2n+1 − 2 n+1 + 1 и b n = 2 2n+1 + 2 n+1 + 1 делится и какое не делится на 5. 9. а) Докажите, что для каждого натурального числа n существует такое натуральное число x, что каждый из членов бесконечной последовательности. делится наб) Докажите, что существует бесконечно много нечетных чисел для которых ни при каком четном x ни одно из чисел бесконечной последовательности. не делится на См. также задачи 4 б) и 10–14 предыдущего раздела. Указания и решения. а) Ответ {−3; −2; 0; Пусть n + 1|n 2 + 1. Тогда n + 1|n 2 + 1 − (n + 1)(n − 1) = 2. Значит + 1 = ±2 или n + 1 = ±1. Тогда находим n = −3, −2, 0 или 1. Проверкой убеждаемся, что все такие значения n подходят Гл. 3. Миникурс по теории чисел Разные задачи. А. Я. Канель-Белов 2000, 5. Существует ли такое целое n, имеющее ровно 2000 различных простых делителей, что 2 n |