федеральное агентство по образованию

государственное образовательное учреждение

высшего профессионального образования

самарский государственный университет

Кафедра алгебры и геометрии

Т. В. Азовская, В. В. Севостьянова

задачи по теории чисел

Утверждено редакционно-издательским

советом университета в качестве

учебного пособия

Самара

Издательство Самарский университет 2009 УДК 511.2 ББК 22.13 А 357 Рецензенты:

канд. физ.-мат. наук, доц. Н. А. Яковлева, канд. физ.-мат. наук, доц. С. Ю. Попов Азовская, Т. В.

А357 Задачи по теории чисел: учебное пособие / Т. В. Азовская, В. В. Севостьянова. Самара: Издательство Самарский университет, 2009. 72 с.

Данное учебное пособие содержит материал теоретического курса и одновременно является задачником по теории чисел. В нем рассматриваются основные определения, понятия, теоремы и алгоритмы теории чисел, а также некоторые прикладные задачи.

Расположение теоретического материала соответствует лекционному изложению курса.

В конце каждого параграфа приводятся упражнения, иллюстрирующие теорию. В последней части пособия содержатся примерные варианты контрольной работы по курсу теории чисел.

Учебное пособие предназначено для студентов 1 и 2 курсов специальностей Математика, Компьютерная безопасность, Математическое обеспечение и администрирование информационных систем.

УДК 511. ББК 22. c Азовская Т.В., Севостьянова В.В., c Самарский государственный университет, c Оформление. Издательство Самарский университет, Оглавление Предисловие................................. 1. Делимость чисел............................. 2. Алгоритм Евклида. Наибольший общий делитель и наименьшее общее кратное............................. 3. Применение алгоритма Евклида.................... 4. Простые и составные числа. Бесконечность множества простых чисел. Основная теорема арифметики................ 5. Непрерывные дроби........................... 6. Теоретико–числовые функции...................... 7. Теория сравнений............................. 8. Теорема Эйлера. Малая теорема Ферма................ 9. Кольцо классов вычетов по модулю m................. 10. Вариации на тему малой теоремы Ферма............... 11. Сравнения первой степени....................... 12. Китайская теорема об остатках. Системы линейных сравнений.. 13. Сравнения с одним неизвестным.................... 14. Квадратичные вычеты. Символ Лежандра.............. 15. Символ Якоби.............................. 16. Порядки (показатели) вычетов и их свойства............ 17. Первообразные корни и индексы.................... Примерные варианты контрольной работы по курсу теории чисел.. Библиографический список........................ Предисловие В первом приближении элементарная теория чисел подразумевает изучение свойств чисел натурального ряда одной из наиболее простых математических систем. Основные результаты, которые принято называть классическими, были полностью доказаны к XIX веку, но несмотря на это здесь осталось большое количество нерешенных и полурешенных задач высокого качества. Эти задачи, как правило, имеют простые математические формулировки, понятные и доступные уже школьнику. Их решения часто стимулируют создание новых математических теорий и определяют концепции развития науки на долгие годы. С одним из блестящих результатов такого сорта вы сможете познакомиться уже на начальном этапе изучения теории чисел. Без сомнения, речь идет о квадратичном законе взаимности, первое полное доказательство которого получил Ф. Гаусс. Другой блестящий пример Великая теорема Ферма.

Пособие представляет собой комплекс теоретического курса и решения задач. Для понимания сути происходящего читателю достаточно знаний средней школы.

В целом при рассмотрении общих вопросов мы старались следовать классическому подходу. Расположение параграфов соответствует лекционному изложению материала. Доказательства большинства теорем, цитируемых в пособии, разбиты на отдельные задачи, решая которые можно самостоятельно получить то или иное утверждение. В конце каждого параграфа приведены упражнения, иллюстрирующие теорию. Задачи повышенной сложности отмечены звездочкой. Несколько слов о трудностях, с которыми может столкнуться студент. Дело в том, что в элементарной теории чисел не так много стандартных приемов, но много задач, которые требуют изобретательности и догадки. В пособии разобран ряд задач, демонстрирующих некоторые трюки.

Осваивайте стандартные алгоритмы, анализируйте нестандартные приемы, разбирайте доказательства только в этом залог вашего будущего успеха!

Особое внимание –– списку используемой литературы, он содержит лучшие, с нашей точки зрения, учебники по элементарной теории чисел. Большая часть упражнений заимствована из этих замечательных книг.

Мы старались не избегать изложения ряда прикладных аспектов элементарной теории чисел, что дало возможность разнообразить задачи и примеры. Содержание курса доказывает свою ценность в целом ряде приложений, связанных, например, с задачами криптографии. Подобные отклонения в области применения теории чисел будут интересны будущим специалистам по компьютерной безопасности.

В тех случаях, когда мы испытывали потребность дать единое толкование ряда фактов, мы обращались к понятиям группы, идеала, фактор кольца.

Такие отступления оказываются весьма полезными при знакомстве с начальными понятиями абстрактной алгебры, поскольку первые примеры здесь связаны, как правило, с арифметикой кольца целых чисел.

При написании этого пособия нам существенно помогли советы наших коллег. Мы выражаем благодарность всем сотрудникам кафедры алгебры и геометрии за внимание к нашей работе. В частности, нам хотелось бы выразить признательность М. В. Игнатьеву за своевременные толковые замечания и Ю. Ю. Крутикову за апробацию нашего пособия.

1. Делимость чисел Пусть a и b целые числа, b = 0. Говорят, что b делит a, если найдется такое целое число c, что a = b · c. Для записи делимости нацело используются стандартные обозначения b|a (b делит a) и a. (a делится на b).

Упражнение. Используя определение, докажите следующие свойства делимости:

a) если a|b и b|c, то a|c;

b) если a|b и b|a, то a = ±b (это свойство полезно при доказательстве равенства чисел с точностью до знака);

c) если a|b и a|c, то a|(b ± c) и a|(k · b) при любом целом k.

Кольцо целых чисел Z одно из колец, в котором имеется алгоритм деления с остатком.

Пусть a, b Z, b = 0. Разделить a с остатком на b означает представить a в виде a = bq + r, где 0 r < |b|. В этой записи q называют неполным частным, а r остатком от деления a на b.

Каждый школьник умеет делить с остатком и хорошо представляет себе правило выбора неполного частного.

Опираясь на "школьный" опыт, докажите следующую теорему существования и единственности деления с остатком:

Теорема. Для любой пары целых чисел a и b, b = 0, a единственным образом представимо в виде a = bq + r, где 0 r < |b|.

Примечание. Начните со случая a > 0, b > 0, а затем, используя доказанное, переберите все возможные варианты для a и b.

Задачи 1. Число n при делении на 16 дает в остатке 3. Какой остаток при делении на 12 даст число 3n?

2. Какие остатки при делении на 24 могут иметь простое число и его квадрат?

3. Какие остатки при делении на p имеют квадраты и кубы целых чисел, Используя результаты задачи, обоснуйте неразрешимость в целых числах уравнений Составьте алгебраические уравнения с целыми коэффициентами второй и третьей степени, не имеющие решений в целых числах.

Воспользуемся свойствами делимости и решим следующую задачу.

Задача. При каких натуральных n сократима дробь Решение. Пусть числитель a = 8n + 71 и знаменатель b = 5n + кратны числу d, тогда d делит 5a 8b = 13. Отсюда получаем, что если дробь сократима, то только на d = 13. Теперь достаточно указать только те значения n, при которых b (или a) делится на 13.

Получаем, что 13 делит 5n + 46 тогда и только тогда, когда 13 делит число 5n + 20, а это в свою очередь равносильно тому, что 13 делит n + 4.

Таким образом, дробь сократима тогда и только тогда, когда остаток от деления числа n на 13 равен 9.

Замечание. Немного позже запись решения подобных задач мы станем воспроизводить, используя язык и свойства числовых сравнений.

Задачи 1. При каких целых значениях n следующая дробь есть целое число:

2. При каких натуральных n сократима дробь ?

3. Известно, что nm + st делится на n + s. Докажите, что число nt + sm 4. Докажите, что из n целых чисел всегда можно выбрать несколько таких чисел, что, поставив между ними знаки ”+” и ” ”, можно получить число, делящееся на n.

5. Целые числа n и m таковы, что m + 3n кратно 13. Докажите, что число 11m + 7n делится на 13.

6. Целые числа n и m таковы, что 2m n кратно 11. Докажите, что число 51m 8n делится на 11. Придумайте свою задачу такого типа.

7. Примените теорию делимости к доказательству равенства чисел:

Составьте свою подобную задачу. Каким условиям удовлетворяют коэффициенты при n и m?

8. Докажите, что число, в десятичной записи которого участвуют пятнадцать единиц и некоторое число нулей, не может быть квадратом целого 9. Каждый из людей, когда-либо живших на Земле, сделал определенное число рукопожатий. Докажите, что число людей, сделавших нечетное число рукопожатий, четно.

10. В ряд записаны числа 1, 2,..., n. Можно ли расставить между ними знаки ”+” и ”” так, чтобы значение полученного выражения было равно нулю? Дайте ответ при n = 17.

11. На столе стоят 15 чашек, все вверх дном. За один ход разрешается перевернуть 4 чашки. Можно ли за несколько ходов добиться того, чтобы чашки стояли правильно?

12. Натуральные числа m, n и k таковы, что mn делится на nm, а число nk делится на k n. Докажите, что число mk делится на k m.

13. Докажите, что следующие числа не являются целыми:

Указание. Обозначим где 2 (m) логарифмическая 2–норма (см. параграф 6 "Теоретико– числовые функции"). Покажите, что среди чисел от 1 до n имеется точно одно, кратное 2k. Представив сумму 1 + +... + в виде несократимой дроби, получите, что при четном числителе знаменатель окажется нечетным.

14. Докажите, что обыкновенная дробь представима в виде конечной десятичной дроби тогда и только тогда, когда n не делится на простые числа, отличные от 2 и 5.

15. Найдите наибольшее натуральное четырехзначное число, все цифры которого различны и которое делится на 2, 5, 9, 11.

16. Докажите, что если a3 + b3 + c3 делится на 7 (a, b, c Z), то abc делится 17. Доказать, что 62k + 2k+4 делится на 17.

2. Алгоритм Евклида. Наибольший общий делитель и наименьшее общее кратное Определение. Назовем наибольшим общим делителем чисел a и b (обозначается НОД(a, b) или (a, b)) такой их общий делитель, который делится на любой другой их общий делитель.

Наименьшим общим кратным чисел a и b (обозначается НОК(a, b) или [a, b]) назовем такое их общее кратное, на которое делится их любое общее кратное.

Для определенности будем считать наибольший общий делитель и наименьшее общее кратное неотрицательными числами.

Мы дали определение наибольшего общего делителя и наименьшего общего кратного на языке делимости. В школе эти понятия часто вводят как наибольший из возможных делителей и наименьшее из возможных кратных соответственно.

Упражнение. Докажите эквивалентность определений наибольшего общего делителя и наименьшего общего кратного на языке абсолютных величин и на языке делимости.

Задача. Примените теорию делимости к доказательству следующего равенства чисел: (n, m) = (5n + 3m, 13n + 8m).

Решение. Введем обозначения:

Очевидно, что d делит числа 5n + 3m и 13n + 8m, отсюда заключаем, что d их общий делитель и, следовательно, d делит D.

Обратно, при некоторых t, s Z. Выразив из этой системы n и m, получим откуда следует, что число D делит d. Из свойств делимости заключаем, что D = ±d.

Одним из самых привлекательных свойств наибольшего общего делителя является простота его вычисления с помощью известного уже более лет метода, называемого алгоритмом Евклида. Суть метода заключается в последовательном выполнении деления с остатком. Делитель и остаток предыдущего шага становятся соответственно делимым и делителем следующего.

Пусть a, b положительные целые числа. Предположим, что a > b, тогда Делимость нацело в последней строке объясняется строгим убыванием и ограниченностью снизу нулем последовательности остатков {rn }. Кроме того, Таким образом, последний ненулевой остаток в алгоритме Евклида, примененного к числам a и b, и есть наибольший делитель этих чисел.

Упражнения 1. Умножив каждую строку в алгоритме Евклида на m, получите утверждение 2. Пусть d общий делитель чисел a и b. Докажите, что 3. Пусть d = (a, b). Докажите, что справедливо равенство С помощью алгоритма Евклида можно получить и нечто большее, чем наибольший общий делитель. Для этого выразим rn из последней строки и будем "подниматься" вверх по строчкам алгоритма Евклида, заменяя на каждом шаге rk на rk2 rk1 qk. В результате мы получим линейное представление наибольшего общего делителя (a, b), то есть представление наибольшего общего делителя в виде для некоторых целых u и v. Знание линейного представления наибольшего общего делителя будет нам полезно при решении ряда задач.

Упражнение. Докажите справедливость равенства (1).

Числа a и b, наибольший общий делитель которых равен (a, b) = 1, называют взаимно простыми числами.

Упражнения 1. Докажите, что числа a и b взаимно просты тогда и только тогда, когда единица представима в виде 2. Докажите утверждение: если (a, b) = 1, то для любого c справедливо 3. Докажите, что если c|ab и (a, c) = 1, то c|b.

4. Докажите, что если (a, b) = 1, a|c и b|c, то ab|c.

5. Используя свойства наибольшего общего делителя и упражнение 4, получите формулу, связывающую наибольший общий делитель и наименьшее общее кратное чисел a и b:

Задача. Найдите все целые решения диофантова уравнения Решение. Заметим, что наше уравнение определяет на плоскости прямую, и перейдем к ее параметрическому уравнению:

(здесь (x0, y0 ) некоторая точка прямой с целыми коэффициентами).

Поскольку (17, 43) = 1, то найдутся целые u и v такие, что В качестве x0 возьмем 2u, тогда y0 = 2v. Найдем u и v из алгоритма Евклида:

прямой с целыми координатами, то Отсюда в силу взаимной простоты чисел 17 и 43 получаем, что 17 делит число y1 y0 и 43 делит x1 x0. Следовательно, точка (x1, y1 ) получается из параметрического уравнения прямой при некотором целом значении параметра t. Верно и обратное: любое целое значение t определяет точку на прямой с целыми координатами.

Получаем ответ: x = 10 43t, y = 4 + 17t, где t любое целое число.

Задачи 1. Какими могут быть числа a и b, если a) НОК(a, b) = 2640 и НОД(a, b) = 15;

b) НОК(a, b) +НОД(a, b) = 35, НОД(a, b) = 1;

c) НОК(a, b) ·НОД(a, b) = 630, НОД(a, b) = 1?

Придумайте свои задачи подобного типа.

2. Найдите наибольший общий делитель следующих пар чисел (1035, 1105), (611, 676), (8183, 1152).

3. Найдите линейное представление наибольшего общего делителя следующих пар чисел (93, 39), (76, 28), (17, 101).

4. Используя линейное представление наибольшего общего делителя, решите в целых числах уравнения 5. Числа m и n взаимно простые. Докажите, что следующие пары чисел взаимно простые:

6. Числа m и n взаимно простые. Какие общие делители могут иметь 7. Докажите, что если (a, b) = 1 и p простое число, то (a + b, a · b · p) = 8. Докажите, что если числа a и b взаимно простые, то наибольший общий делитель чисел a · c и b равен наибольшему общему делителю 9. Докажите, что если (a, b) = d, то (a + b · c, a + b(c 1)) = d.

10. Установите, чему может быть равно наименьшее общее кратное трех последовательных натуральных чисел.

11. Пусть p простое число. Докажите, что для n = 1, 2,..., p 1 числа n и p n взаимно просты.

12. Пусть rn n-значное число вида 111... 11. Докажите, что 13. Докажите, что два различных числа Ферма 22 + 1 и 22 + 1 взаимно 15. Докажите, что если n 16. Найдите отношение, если известно, что для всех натуральных k выполняется условие v 3. Применение алгоритма Евклида Пусть A произвольное коммутативное кольцо.

Определение. Непустое подмножество I в A называется идеалом, если оно обладает двумя свойствами:

1. Из x1, x2 I следует, что x1 x2 I.

2. Из x I следует, что ax I для любого элемента a A.

Нетрудно убедиться, что произвольное конечное множество a1, a2,..., as элементов кольца A определяет идеал I, состоящий из элементов кольца, представимых в виде линейных комбинаций i ai с коэффициентами i из A.

В этом случае говорят, что идеал порожден {ai }s и пишут Идеал, порожденный одним элементом I = (a), называется главным.

Алгоритм деления с остатком позволяет легко установить, что любой идеал в кольце целых чисел главный идеал. В качестве образующей идеала I в кольце Z следует взять наименьшее неотрицательное число в I (проведите рассуждения полностью).

Задачи 1. Пусть d =НОД(a1, a2,..., as ). Докажите, что 2. Найдите необходимое и достаточное условие разрешимости в целых числах уравнения ax+by = c и, шире, уравнения a1 x1 +a2 x2 +...+as xs = b.

3. Множество натуральных чисел разбито на два подмножества A и B так, что A · B (то есть множество всех произведений ab, где a A, b B) содержится в A и A + B (то есть множество всех сумм вида a + b, где b) A состоит из всех чисел, кратных некоторому числу d.

4. Пусть (a, b) = 1. Докажите, что любую сумму, начиная с (a 1)(b 1), можно уплатить монетами достоинством a и b таньга, а сумму 4. Простые и составные числа.

Бесконечность множества простых чисел.

Основная теорема арифметики Одно из основных понятий в теории чисел понятие простого числа.

Напомним, что натуральное число p называется простым, если оно имеет ровно два натуральных делителя, а именно, 1 и p. Все другие натуральные числа называются составными. Единица по определению не является ни простым, ни составным числом.

Упражнение. Покажите, что наименьший простой делитель числа n не больше n.

Теорема. Простых чисел в натуральном ряду бесконечно много.

Доказательство, которое мы приведем, принадлежит Евклиду. Оно проводится методом "от противного". Следует рассмотреть число где p1, p2,..., ps список всех простых чисел, и показать, что у него, с одной стороны, нет простых делителей, а с другой стороны, оно не может быть простым.

Поскольку единственное четное простое это двойка, то теорему Евклида можно сформулировать иначе.

Теорема. В арифметической прогрессии nk = 2k + 1, где n0 = 1, с разностью равной 2, существует бесконечно много простых.

Обобщает теорему Евклида замечательный результат Дирихле.

Теорема (о простых числах в арифметических прогрессиях).

Любая арифметическая прогрессия ak + b, где a и b целые числа, число k целое неотрицательное, содержит бесконечно много простых чисел.

Доказательство этой теоремы в общем случае проводится далеко не элементарными методами, однако некоторые частные случаи теоремы Дирихле можно достаточно легко получить.

Упражнение. Докажите, что существует бесконечно много простых вида 4k + 3, k целое неотрицательное.

Указание. Восстановите доказательство по следующему плану.

1. Нечетное простое при делении на 4 дает в остатке 1 или 3; если все простые pi 1 (mod 4), то 2. Пусть 3, p1, p2,..., ps все простые из прогрессии 4k + 3, k = 0, 1, 2,...

Число N = 4p1 p2... ps + 3 не может быть простым и обязано делиться Задача. Опираясь на теорему Дирихле, покажите, что для каждого натурального m существует простое число, сумма цифр которого больше, чем m.

Решение. Рассмотрим арифметическую прогрессию где k целое неотрицательное. Сумма цифр любого числа построенной прогрессии больше, чем m, следовательно, простые числа в данной прогрессии удовлетворяют нужному свойству.

Завершая обсуждение теоремы Евклида, обратим внимание читателей на замечательную книгу П. Рибенбойма [2]. В ней приводится более десятка различных доказательств бесконечности множества простых чисел.

Место следующей теоремы в элементарной теории чисел определено самим ее названием.

Основная теорема арифметики. Каждое натуральное число n > может быть однозначно записано в виде произведения степеней простых чисел:

где pi различные простые делители числа n, i N.

Представление числа n в виде произведения примарных взаимно простых множителей называется каноническим разложением числа n.

Задачи 1. Докажите, что для того, чтобы нечетное натуральное число n было простым, необходимо и достаточно, чтобы представление n в виде x2 z было единственным.

2. Докажите, что среди целых чисел, представимых многочленом положительной степени с целыми коэффициентами, имеется бесконечно много составных.

3. Пусть Mn = 2n 1 и Mm = 2m 1 два числа Мерсенна, r остаток от деления n на m. Покажите, что остаток от деления Mn на Mm равен числу Mr. Получите необходимое условие простоты чисел Мерсенна.

4. Докажите следующий критерий простоты натурального числа n > 1:

натуральное число n является простым тогда и только тогда, когда для любой пары натуральных чисел a и b такой, что n|(a · b), следует, что 5. Докажите теорему о бесконечности множества простых чисел, используя факт взаимной простоты чисел Ферма:

6. Для натуральных n и k докажите, что если 2n > (1+n)k, то среди чисел 1, 2, 22,..., 2n существует по крайне мере k+1 простое число. Покажите, что отсюда следует бесконечность множества простых чисел.

7. Докажите, что среди чисел {1, 2,..., n} не менее четверти свободны от квадратов. Получите из этого утверждения доказательство бесконечности множества простых чисел.

8. Опираясь на теорему Дирихле о простых числах в арифметических прогрессиях, докажите, что для всякого натурального числа n найдется простое число p такое, что каждое из чисел p 1 и p + 1 имеет не более чем n различных делителей.

9. Докажите, что в натуральном ряду существуют сколь угодно большие промежутки, не содержащие простых чисел.

Указание. Рассмотрите следующий ряд:

5. Непрерывные дроби Рассмотрим рациональную дробь Q. Без ограничения общности будем считать, что a > b. Благодаря алгоритму Евклида рациональное может быть единственным образом записано в виде конечной непрерывной дроби:

где qk неполные частные, а rk остатки из алгоритма Евклида.

Имеет место следующее Утверждение. Разложение в непрерывную дробь рационального числа конечно.

Любая конечная непрерывная дробь является рациональным числом.

Следующую дробь будем называть k-й подходящей дробью:

Будем считать, что P1 = 1, Q1 = 0, 0 = q0, отсюда P0 = q0, Q0 = 1, тогда Упражнение. Покажите, что найдите P4, Q4.

Упражнение. Покажите индукцией по k, что числитель и знаменатель (k + 1)-й подходящей дроби при k 2 могут быть найдены с помощью рекуррентного соотношения:

О свойствах подходящих дробей можно прочитать, например, в [4].

При решении задач нам особенно полезно будет свойство, выражающее связь числителей и знаменателей двух соседних подходящих дробей, а именно:

Упражнение. Докажите индукцией по k приведенное выше свойство.

Все подходящие дроби несократимы, а последняя подходящая дробь совпадает по значению с рациональным числом:

Поэтому, если наша дробь несократима, то есть (a, b) = 1, получаем При решении задач о нахождении целочисленных решений уравнений вида ax + by = c удобно пользоваться соотношением (2).

Найдем решения в целых числах уравнения ax + by = c.

Предположим, что (a, b) = 1. Решение (x, y) нашего уравнения будем искать в виде где (x0, y0 ) частное решение уравнения ax + by = c, а (x1, y1 ) решение уравнения ax1 + by1 = 0.

Разложим в непрерывную дробь число. Умножим равенство на число (1)n1 c; получим Таким образом, в качестве частного решения ax + by = c возьмем Решением уравнения ax + by = 0 является Таким образом, множество целочисленных решений состоит из чисел вида Пусть теперь (a, b) = d > 1. Тогда, если число d не делит c, уравнение ax + by = c не имеет решений. Если же d > 1 является наибольшим общим делителем чисел a, b, c, следует решать уравнение где a = da1, b = db1 и c = dc1.

Упражнения 3. Решите уравнения 4. Найдите все целочисленные решения уравнений Задачи 1. Докажите, что Pk1 Qk+1 Pk+1 Qk1 = (1)k qk+1.

2. Пользуясь предыдущей задачей, покажите, что последовательность подходящих дробей с четными индексами возрастающая, а последовательность подходящих дробей с нечетными индексами убывающая, то выполняется qi = q. Докажите, что при k < n Будем рассматривать бесконечные дроби вида [q0 ; q1, q2,...], где qk > это целые числа. Такая дробь называется периодической, если существуют такие натуральные N и T, что при k N. В этом случае мы будем обозначать периодическую часть в символе дроби чертой сверху, то есть Задачи 1. Найдите значение дроби [1; 1].

2. Найдите значения следующих дробей:

3. Докажите равенство: если a 2 натуральное число, то 6. Теоретико–числовые функции Для всех функций этого параграфа область определения множество Z или N.

Логарифмическая p-норма Определение. Пусть натуральное число n таково, что n = pm s, где p простое, (p, s) = 1, тогда функция p (n) = m называется логарифмической p-нормой, или функцией порядка или p-адическим показателем.

Приведем некоторые свойства функции порядка:

A. p (ab) = p (a) + p (b).

B. p (a+b) min {p (a), p (b)}, если же p (a) = p (b), то равенство точное.

C. p (a) = 0 тогда и только тогда, когда (a, p) = 1.

D. p (p) = 1.

E. Положим по определению p (0) =.

Упражнение. Докажите свойства A C функции порядка.

При вычислении логарифмической p-нормы от чисел вида n! удобно использовать следующее утверждение.

Задача. Покажите, что показатель, с которым число p входит в разложение числа n!, равен Здесь [x] обозначает целую часть числа x.

Замечание. В действительности сумма, приведенная в задаче, содержит лишь конечное число ненулевых слагаемых, поскольку с некоторого момента целые части начнут обращаться в нуль.

Мультипликативные функции Определение. Функция f : N C называется мультипликативной, если она удовлетворяет условиям:

A. Существует такое натуральное число a0, что f (a0 ) = 0.

B. Для любых натуральных взаимно простых чисел a и b выполняется равенство f (ab) = f (a)f (b).

Мультипликативную функцию достаточно задать на примарных числах, так как в силу мультипликативности она однозначно продолжается на все множество N.

Задача. Докажите, что справедливы следующие свойства мультипликативных функций:

A. f (1) = 1.

мультипликативна.

Утверждение. Пусть f (n) мультипликативная функция, каноническое разложение числа n:

тогда где суммирование ведется по всем делителям d числа n, а произведение по всем простым pi, делящим n.

Доказательство. Чтобы доказать это тождество, раскроем скобки в правой части равенства. Получим сумму слагаемых вида причем ни одно слагаемое не будет пропущено и не повторится более одного раза, а это в точности то, что записано в левой части равенства.

Упражнение. Докажите тождество если n = p1 p2... ps каноническое разложение числа n.

В качестве примеров мультипликативных функций рассмотрим следующие.

Сумма делителей числа n Сумму делителей числа n обозначают Число делителей числа n Число делителей числа n обозначают Упражнения 1. Найдите (n) и (n), где n = 14, 10, 63, 270, 300.

1. Пусть n = p1 p2... pk. Докажите формулы 2. Покажите, что (n) и (n) мультипликативные функции.

Функция Мебиуса заданная на множестве Z>0 условием Доказательство. Поскольку µ(n) мультипликативная функция, то f1 (n) = µ(n)f (n) также мультипликативна. Применим к ней (3): поскольку f1 (p) = f (p) и f1 (ps ) = 0 при s > 1, убеждаемся в справедливости нашего утверждения.

1. Докажите, что при n > 1 справедливо равенство Утверждение 2. Пусть целым положительным соответствуют любые вещественные или комплексные n = n1, n2,..., ns.

Обозначим через S сумму значений n, соответствующих, равным единице, и через Sd сумму значений n, отвечающих, кратным d. Тогда где d пробегает все целые положительные числа, делящие хотя бы одно значение.

Доказательство. Из задачи 2 следует, что Собирая члены с одним значением d и вынося µ(d) за скобки, в скобках получим сумму тех и только тех n, у которых соответствующие им кратны d.

Эта сумма в точности равна Sd.

Функция Эйлера Определение. Функция Эйлера (n) определена на множестве целых положительных чисел и принимает значение, равное количеству чисел ряда взаимно простых с n.

Упражнения 1. Вычислите по определению значение функции Эйлера (n) для Доказательство. Применим формулу (5). При этом числа и n определим следующим образом: пусть x пробегает множество чисел 0, 1,..., n1;

каждому значению x поставим в соответствие число = (x, n), получим S0,..., Sn1 ; возьмем все значения ni равными 1.

Тогда S равно числу значений = (x, n), равных 1, то есть S = (n).

Число Sd равно числу значений = (x, n), кратных d. Заметим, что число d делит (x, n) только в случае, когда d делитель n. Тогда Sd будет равна числу значений x, кратных d, то есть Sd =. В результате в силу (4) получим что завершает доказательство утверждения.

Упражнение. Найдите (362), (2004).

Задача. Докажите, что Задачи 1. Найдите наименьшее натуральное число n, для которого (n) = 6.

2. Докажите, что (n) нечетно тогда и только тогда, когда n квадрат целого числа.

3. Докажите, что (n) нечетно тогда и только тогда, когда n квадрат или удвоенный квадрат целого числа.

4. Покажите, что r простое тогда и только тогда, когда (r) = r + 1.

5. Решите уравнения 6. Докажите следующее равенство:

7. Покажите, что для функции Эйлера выполняются следующие свойства:

b) (n) четно, если n > 2;

c) (m)(n) = ((m, n)) ([m, n]).

8. Некоторое натуральное число имеет 3 простых делителя, квадрат этого числа имеет 27 делителей. Сколько делителей имеет куб этого числа?

9. Что больше:

a) (mn) или (m)(n);

10. Решите уравнения в целых положительных числах 11. Докажите, что если (n) простое число, то n = 3, 4 или 6.

12. Покажите, что если m делит n, то (m · n) = m · (n).

13. Покажите, что если n не является квадратом целого числа.

14. Используя свойства (n), покажите, что простых чисел бесконечно много.

15. Докажите формулу обращения Мебиуса: пусть 7. Теория сравнений Мы уже использовали понятие модуля, рассматривая остатки от деления на 2, 4, 10,... Интуитивно мы понимаем, что очень часто сравнение чисел только по величине остатка от деления на некоторое число m приводит нас к нужному результату.

Определение. Фиксируем целое число m, отличное от 0 и 1. Будем говорить, что два целых числа a и b сравнимы по модулю m, если выполняется одно из трех эквивалентных условий:

• a и b имеют одинаковые остатки при делении на m;

• m делит разность a b;

• a = b + mt для некоторого целого t.

Упражнение. Установите эквивалентность приведенных выше условий.

Для обозначения условия "a сравнимо с b по модулю m" используется следующая запись: a b (mod m).

Исторически понятие сравнения было введено Гауссом, оно является ярким примером использования "правильного" обозначения. Поскольку для любой пары целых a и b выполняется или не выполняется условие то сравнимость по модулю m определяет на Z бинарное отношение. Легко проверить, что данное отношение рефлексивно, симметрично и транзитивно и, следовательно, является отношением эквивалентности. Таким образом, все множество Z можно представить в виде объединения непересекающихся классов чисел, сравнимых по модулю m. Каждый класс сравнимых по модулю m чисел назовем классом вычетов по модулю m. Каждый класс вычетов однозначно определяется любым своим представителем.

Наименьший неотрицательный представитель класса вычетов это остаток от деления на m чисел данного класса.

Введем следующие стандартные обозначения: классом элемента a (обозначается a или [a]) назовем множество a + mZ.

Определение. Назовем любое множество представителей, взятых по одному из каждого класса вычетов по модулю m, полной системой вычетов по модулю m.

Если b1,..., bm любая полная система вычетов, то Определение. Подмножество полной системы вычетов, состоящее из всех вычетов, взаимно простых с m, назовем приведенной системой вычетов по модулю m.

Упражнение. Покажите, что в приведенной системе вычетов по модулю m имеется (m) представителей.

Свойства делимости на m, сохраняющиеся при арифметических операциях с целыми числами, удобно записывать на языке числовых сравнений.

Утверждение. Справедливы следующие свойства числовых сравнений:

A. a a (mod m).

B. Если a b (mod m) и b c (mod m), то a c (mod m).

C. Пусть a b (mod m) и c d (mod m), тогда a ± c b ± d (mod m).

D. Если a b (mod m), то a + k b + k (mod m) для любого k Z.

E. Пусть a b (mod m) и c d (mod m), тогда ac bd (mod m).

F. Пусть a b (mod m), тогда для любого целого k справедливо G. Пусть a b (mod m), тогда для любого n N an bn (mod m).

I. Пусть P (x) многочлен с целыми коэффициентами степени n и Упражнение. Докажите приведенные свойства.

Рассмотрим уравнение f (x1, x2,..., xn ) = 0, где уравнения, тогда из условия следует, что для любого m выполняется сравнение Вопрос о разрешимости сравнения может быть выяснен за конечное число шагов. Для этого в качестве значений переменных нужно перебрать некоторые полные системы вычетов по модулю m. Если удастся предъявить такой модуль, что сравнение (6) окажется неразрешимым, тогда и уравнение не будет иметь решений в целых числах.

Такую методику решения задач называют методикой выбора модуля.

В качестве примера приведем решение следующей задачи.

Задача. Даны две последовательности целых чисел:

Возможно ли при каких-нибудь k и l совпадение xk и yl ?

Решение. Покажем, что по модулю 101 последовательности постоянны и различны. Вычислим x3 = 111, x4 = 1121, y3 = 91 и y4 = 919. Нетрудно видеть, что при i 3 выполняется Докажем методом математической индукции, что последовательности {xi } и {yi } постоянны по модулю 101. Выполнение базы индукции очевидно. Пусть xn+1 = (xn + 1) xn1 + 1 10 (mod 101), тогда Аналогично, yn 10 (mod 101).

Таким образом, никакие два числа последовательностей {xi } и {yi } не совпадают по модулю 101, следовательно, никакие {xl } и {yk } не совпадают Упражнения 1. Верны ли следующие числовые сравнения:

2. Укажите наименьшее положительное число, с которым сравнимо число Как можно охарактеризовать наименьшее неотрицательное число, сравнимое с числом a по модулю m?

3. Укажите наименьшее по абсолютной величине число, с которым сравнимо число a по модулю m:

Опишите способ получения этого числа.

4. Используя свойства числовых сравнений, найдите наименьшее положительное x, удовлетворяющее условию:

5. Найдите остаток от деления на m выражения 3x9 + 5y 3 4z 5 :

b) m = 31, x 2 (mod 31), y 28 (mod 31), z 25 (mod 31).

Сформулируйте свойства сравнений, использованные при решении этой задачи.

Задачи 1. Покажите, что по модулю 8 числа 64, 14, 38, 1, 4, 11, 25, 3 составляют полную систему вычетов, а числа 17, 11, 33, 19 приведенную систему вычетов.

2. Покажите, что числа 36, 11, 10, 9, 2, 11 составляют полную систему вычетов по модулю 6. Выберите вычеты, составляющие приведенную систему вычетов по модулю 6.

3. Запишите полную систему вычетов по модулю 7, наименьших по абсолютной величине.

4. Для каких модулей числа a и a попадают в один и тот же класс вычетов?

5. Назовем натуральное простое число абсолютно простым, если при любой перестановке его цифр снова получается простое число. Докажите, что в записи абсолютно простого числа не может быть использовано более трех различных цифр.

6. Докажите, что если (a, m) = 1 и x пробегает полную систему вычетов по модулю m, то ax + b тоже пробегает полную систему вычетов по модулю m.

7. Докажите, что остаток от деления любого числа на 3 или 9 совпадает с остатком от деления на 3 или 9 суммы цифр данного числа.

8. Получите признак делимости на 11.

9. Записав число в системе счисления с основанием 100, получите признак делимости на 101.

10. Записав число в системе счисления с основанием 1000, получите признаки делимости на 13, 7 и 37.

11. Докажите, что если m|(a b), то для любого n > 1 выполняется равенство 12. Докажите, что 13. Пусть p нечетное простое число. Дано p1 целых чисел, не делящихся на p. Докажите, что, заменив некоторые из этих чисел на противоположные, можно получить p 1 чисел, сумма которых кратна p.

14. Докажите, что сумма квадратов пяти последовательных положительных целых чисел не является квадратом целого числа.

Указание. Покажите, что сумма кратна 5 и не делится на 25.

15. Докажите, что если n сумма квадратов целых чисел, то n при делении на 4 дает в остатке 0, 1 или 2.

Замечание. Полное описание чисел, являющихся суммами двух квадратов, нашел Ферма, а доказательство этого утверждения первым получил Эйлер.

16. Докажите, что сумма 22 + 44 + 66 +... + 5050 не является квадратом целого числа.

17. Найдите n N, для которых число 1! + 2! +... + n! квадрат целого 18. Докажите, что число 11 +22 +33 +...+20072007 не может быть степенью целого числа.

простое.

20. Докажите, что если n сумма трех квадратов целых чисел, то n при делении на 8 не может давать в остатке 7.

Замечание. Полное описание чисел, являющихся суммами трех квадратов, получил Гаусс. Лагранж доказал, что любое натуральное число есть сумма четырех квадратов целых чисел [2].

21. Ферма высказал гипотезу, что для всех целых натуральных чисел n число 22 + 1 является простым. Эйлер нашел пример, опровергающий эту гипотезу: число 641 делит 232 + 1. Подтвердите это, используя сравнения.

22. Найдите все арифметические прогрессии из пяти простых положительных чисел с разностью 6.

23. Найдите наибольшее число членов в конечной арифметической прогрессии, состоящей их простых чисел.

8. Теорема Эйлера. Малая теорема Ферма Теорему, о которой мы будем говорить в этом разделе, называют "малой теоремой Ферма". Частный случай этой теоремы известен сотни лет, но Ферма, вероятно, был первым, кто доказал эту теорему в полной общности.

Малая теорема Ферма. Пусть p простое число, (a, p) = 1, тогда Следствие. Для любого целого a выполняется Эйлер обобщил результат Ферма на случай составного m.

Теорема Эйлера. Пусть (a, m) = 1, тогда Упражнение. Восстановите доказательство теоремы Эйлера, используя следующие свойства:

1. Умножение приведенной системы вычетов по модулю m на число a приводит к приведенной системе вычетов.

2. Произведения элементов двух любых приведенных систем вычетов по модулю m сравнимы по модулю m.

3. Сравнения можно делить на числа, взаимно простые с модулем m.

Задачи 1. Запишите и проверьте теорему Эйлера для следующих пар чисел:

2. Запишите и проверьте теорему Ферма для следующих пар чисел:

3. Сколько решений, то есть классов вычетов по модулю m, имеет сравнение xp1 1 (mod p)?

4. Найдите остатки от деления 7122 на 143, 8900 на 29.

5. Докажите теорему Вильсона: (p 1)! 1 (mod p), где p простое 6. Найдите простые числа p, для которых следующие числа простые:

Придумайте свою задачу такого типа.

7. Покажите, что для нечетных n 8. Существует ли 99-значное число a такое, что число aa делится на a2 ?

9. Докажите, что для любого натурального числа n, (n, 10) = 1, существует число вида 111... 1, кратное n. Назовите минимальное число разрядов числа 111... 1, кратного n.

10. Докажите, что если a1 + a2 +... + as 0 (mod 30), то Придумайте свою подобную задачу.

11. Докажите, что (a + b)p ap + bp (mod p), где p простое, a любое целое число.

12. Пусть a и b взаимно простые числа. Докажите, что 9. Кольцо классов вычетов по модулю m Множество классов вычетов по модулю m обозначают через Множество Zm можно превратить в кольцо, определив сложение и умножение естественным образом. Если a, b Zm, то сумму двух классов вычетов a + b мы определим как a + b и произведение a · b как a · b.

Упражнение. Используя свойства числовых сравнений, покажите, что результаты определенных таким образом операций сложения и умножения классов вычетов по модулю m зависят лишь от классов вычетов, определяемых a и b.

Упражнение. Покажите, что Zm с введенными операциями кольцо.

Приведенные ниже таблицы в явном виде задают сложение и умножение в кольце Z6 :

Определение. Ненулевые элементы кольца называются делителями нуля, если их произведение равно нулю.

Определение. Элемент a называется обратимым в кольце Zm, если для него существует b Zm такой, что a · b = 1.

Упражнение. Покажите, что a Zm обратим тогда и только тогда, когда (a, m) = 1.

Упражнение. Покажите, что произведение обратимых элементов кольца обратимо.

Обратимые элементы кольца классов вычетов образуют группу по умножению, которая называется мультипликативной группой кольца и обозначается Z.

Упражнение. Покажите, что мультипликативная группа кольца классов вычетов содержит (m) элементов.

Пусть p простое число. В этом случае кольцо Zp не имеет делителей нуля, каждый ненулевой элемент Zp обратим, следовательно, Zp поле классов вычетов.

Замечание. При решении арифметических задач иногда бывает удобнее работать с кольцом Zm, чем с понятием сравнения по модулю m. Так, решение сравнения эквивалентно нахождению обратного к a в кольце Zm ; существование первообразного корня по модулю p (см. параграф "Первообразные корни") означает, что группа Z циклическая, то есть состоит из степеней некоторого одного элемента.

Задача. Для кольца Z/24Z выпишите делители нуля и обратимые элементы. Составьте таблицу умножения для Z, по ней укажите пары взаимно обратимых элементов.

10. Вариации на тему малой теоремы Ферма Приведет ли к успеху попытка обратить малую теорему Ферма? Китайские математики около 2000 тысяч лет назад ошибочно полагали, что если число 2n 2 кратно n, то оно простое. Сейчас такие числа называют псевдопростыми по базе 2.

Определение. Псевдопростыми по базе a называют такие составные числа n, для которых 2n 2 кратно n.

Числа, псевдопростые по любой базе, называются абсолютно псевдопростыми или числами Кармайкла.

Задачи 1. Доказать, что если число n не свободно от квадратов, то есть p2 делит n для некоторого простого p, то n не является псевдопростым по базе 2. Докажите, что для любого a существует бесконечно много псевдопростых по базе a чисел, являющихся составными. Такими являются, наприa2p мер, все числа из последовательности 2, где p простое, n > и p, a2 1 = 1. Найдите наименьшее псевдопростое по базе 2.

3. Покажите, что множество является подгруппой в (Z/nZ).

4. Покажите, что если n не является псевдопростым по основанию хотя бы одного числа a, то Ниже приведена теорема, играющая важную роль в некоторых алгоритмах распознавания простоты и построения больших простых чисел.

Теорема Люка. Пусть N > 1 и нашлось целое число a со свойствами:

2) am не сравнимо с 1 по модулю N для m = 1, 2,..., N 2.

Тогда число N является простым.

Замечание. Обратите внимание, что условие 1 в теореме Люка малая теорема Ферма. Поскольку во многих классических учебниках по теории чисел эта теорема отсутствует, приведем здесь ее доказательство.

Доказательство. Заметим, что (N ) N 1. Далее, поскольку то (a, N ) = 1. Кроме того, ord a делит число (N ). Из условия 2 следует, что ord a = N 1, следовательно, (N ) = N 1. Таким образом, N число простое.

Задача. Покажите, что условие 2 теоремы Люка достаточно потребовать только для всех m, делящих N 1.

11. Сравнения первой степени Пусть f (x) = an xn + an1 xn1 +... + a0 многочлен с целыми коэффициентами. Будем рассматривать сравнение вида Заметим, что если некоторый вычет b удовлетворяет сравнению (7), то все числа, сравнимые с b по модулю m, также удовлетворяют (7). Таким образом, под решением сравнения (7) понимается класс вычетов такой, что Рассмотрим важный частный случай:

Введем следующие обозначения:

Если d делит b, то обозначим b = db. Будем различать три случая:

1. Если (a, m) = 1, то сравнение (8) имеет единственное решение (в смысле класса чисел по модулю m).

2. Если (a, m) = d > 1 и свободный член b не делится на d, то сравнение не имеет решений.

3. Если (a, m) = d > 1 и d делит b, то сравнение имеет d различных решений, которые находятся по формуле где k = 0, 1,..., d 1; число удовлетворяет сравнению которое получается из исходного делением всех членов сравнения (8) Упражнение. Восстановите доказательства трех случаев по следующим кратким указаниям, расположенным в том же порядке, что и номера приведенных выше пунктов.

• Пусть c1, c2,..., cm некоторая полная система вычетов по модулю m.

Тогда в полной системе вычетов ac1, ac2,..., acm найдется ровно один представитель, сравнимый с b по модулю m.

• Если число удовлетворяет сравнению (8), то a b (mod d). Отсюда получаем, что 0 b (mod d), что противоречит условию.

• Заметим, что для числа справедливо тогда и только тогда, когда Сравнение a x b (mod m ) имеет ровно одно решение x (mod m ), то есть всякое решение сравнения (8) однозначно определено по модулю m.

Покажем, что d вычетов k = +m k, где k = 0, 1,..., d1, удовлетворяют исходному сравнению и различны по модулю m.

Поскольку третий случай сводится к первому делением на d, то укажем методы решения сравнения (8) для взаимно простых a и m.

Применяются следующие способы решения:

1. Метод испытаний полной системы вычетов по модулю m.

2. Способ Эйлера, при котором решение находится по формуле 3. При помощи конечных непрерывных дробей по формуле где Pn1 числитель предпоследней подходящей дроби при разложении числа в непрерывную дробь.

4. При помощи преобразования правой части сравнения, а именно, замены вычета b другим вычетом того же класса, но кратным коэффициенту a.

Проведя подобную замену и разделив обе части равенства на a, получаем x.

Задача. Решите сравнение Решение. Проведем анализ: (6, 51) = 3, правая часть кратна 3, следовательно, имеем дело со случаем 3. Разделим обе части сравнения, включая модуль, на 3. Получим 2x 13 (mod 17) или 2x 4 (mod 17). Поскольку (2, 17) = 1, наше сравнение эквивалентно сравнению Отсюда по формуле 3 имеем xk 2 + 17k (mod 51), где k = 0, 1, 2.

Ответом будут следующие три класса вычетов:

Задача. Решите сравнение Решение. Проведем анализ: (17, 151) = 1, следовательно, сравнение имеет единственное решение. Будем решать сравнение с помощью непрерывных дробей. Запишем число в виде непрерывной дроби = [8; 1, 7, 2]; здесь n = 3, Воспользуемся формулой Задача. Решите сравнение методом Эйлера:

Решение. Заметим, что 93 8 (mod 17), поэтому наше сравнение равносильно следующему:

По формуле Эйлера получаем Воспользуемся теоремой Эйлера: 216 1 (mod 17), отсюда x 214 (mod 17).

Заметим, что 24 1 (mod 17), следовательно, Окончательно получаем x 22 4 (mod 17).

Ответ: x 4 (mod 17).

Замечание. Если бы не был указан способ, которым следует решать задачу, то разумнее было бы поступать следующим образом. Заметим, что поэтому сравнение 8x 2 (mod 17) равносильно 8x 32 (mod 17). Разделив на 8, получаем ответ 12. Китайская теорема об остатках.

Системы линейных сравнений Согласно историческим данным, китайская теорема об остатках была известна еще в I веке до н. э.

попарно взаимно простых чисел, а r1, r2,..., rs произвольные числа. Тогда система сравнений имеет единственное решение по модулю M = m1 m2... ms.

Другими словами, набор остатков от деления на попарно взаимно простые числа позволяет восстановить число с точностью до слагаемого, кратного M.

В процессе доказательства теоремы строится вычет, удовлетворяющий системе сравнений.

Для этого обозначим тогда (Ni, mi ) = 1 и найдутся целые di и li, для которых выполнено Переходя к сравнениям, получаем, что для любого i = 1, 2,..., s справедливо Рассмотрим вычет Приведем a по модулю mi при любом i:

Очевидно, что x a (mod M ) решение системы (9).

Упражнение. Покажите, что любые два вычета, удовлетворяющие системе (9), лежат в одном классе по модулю M.

Задача. Используя доказательство китайской теоремы об остатках, постройте решение системы Очевидно, что таким способом удастся решить далеко не всякую систему линейных сравнений.

В качестве универсального способа решения системы линейных сравнений можно указать один очень древний алгоритм. Он применялся еще в античности для решения проблем астрономии. Суть этого метода раскрывается в решении следующей задачи. Рассмотрим систему Для первого сравнения имеем единственное решение Вычеты этого класса следующие: x = 4 + 7t, t Z. Найдем решение первого сравнения, которое одновременно удовлетворяет и второму:

Разделив на 2, получим то есть t = 5s, s Z. Итак, первым двум сравнениям удовлетворяют вычеты вида x = 4 + 7 · 5 · s. Подставим это выражение для x в третье сравнение:

Откуда получаем, что s 1 (mod 2) и s = 1 + 2v.

Окончательно x = 4 + 35s = 39 + 70v или x 39 (mod 70). По модулю система имеет два решения:

Замечание. Если на некотором шаге мы получаем сравнение, не имеющее решений, то это означает, что система несовместна.

При работе с большими модулями китайская теорема об остатках существенным образом помогает упростить вычисления.

Рассмотрим такую задачу.

Задача. Найдите остаток от деления 735286 на 2431.

Решение. Заметим, что применение теоремы Эйлера и приведение основания степени по модулю m нисколько не упрощает вычислений.

Разложим 2431 на множители. Перейдем от сравнения Здесь к каждому из сравнений можно уже применить малую теорему Ферма и уменьшить основание степени по соответствующему модулю Получаем эквивалентную систему Преобразуя правую часть этой системы, имеем:

Таким образом, получаем систему линейных сравнений Решим ее описанным выше способом: x = 4 + 13t, 4 + 13t 2 (mod 11), следовательно, t 3 (mod 11), откуда x = 4 + 13(3 + 11s). Далее следовательно, s = 17k.

Окончательно Остаток от деления это наименьший неотрицательный вычет класса, то есть 2396.

Опишем здесь еще одно интересное применение китайской теоремы об остатках. С долей юмора С.Коутинхо называет эту ипостась китайской теоремы "безопасной системой допуска живых к секретным сведениям".

Проблема здесь такова: имеется пароль или код, который можно считать большим натуральным числом N. Мы хотим распределить этот код между участниками так, чтобы каждый из них что–то знал об N. Для этого нам понадобится k больших попарно взаимно простых чисел mi, удовлетворяющих условию m1 m2... mk > N. Каждому из участников сообщается свой фрагмент кода, состоящий из пары чисел: числа mi и ri остатка от деления N на mi. При наличии всех фрагментов код восстанавливается как наименьшее положительное решение системы В отсутствии хотя бы одного участника мы знаем только арифметическую прогрессию членом которой является код. Чтобы восстановить пароль, следует провести Интересно и доступно об этом приложении китайской теоремы об остатках написано в [6].

Попробуйте решить следующую задачу.

Задача. Имеется три фрагмента пароля, модули фрагментов последоваn тельные числа Ферма: Fn, Fn+1, Fn+2 (напомним, что Fn = 22 + 1). Если двое втайне от третьего захотят вскрыть пароль, то сколько вариантов им придется перебрать?

Задачи 1. Решить системы сравнений:

2. При каких значениях a следующая система сравнений совместна:

3. Найти наименьшее натуральное число, которое при делении на n дает остаток n 1, а при делении на n + 1 дает остаток n.

4. Упростив выражения с помощью китайской теоремы об остатках, решить следующие задачи:

a) найти остатки от деления 129613 на 1001, 359204 на 646, 3950 на b) найти обратный к 347 по модулю 935.

5. Даша гадает на ромашке: "Любит не любит, плюнет поцелует, к сердцу прижмет к черту пошлет". Глаша при гадании к этим шести вариантам добавляет еще свой: "Своей назовет". На ромашках с n и 2n лепестками у Даши хорошее предсказание, а у Глаши плохое.

Чему равно n, если считать, что на ромашке не может быть более лепестков?

6. Покажите, что система не может иметь более одного решения по модулю наименьшего общего 7. Решите сравнение x2 + 42x + 21 0 (mod 105).

8. Пусть p и q различные простые числа и n = pq. Предположим, что мы знаем решение уравнений x2 a (mod p) и x2 a (mod q).

Покажите, как китайский алгоритм остатков можно использовать для решения сравнения x2 a (mod n).

13. Сравнения с одним неизвестным Если m = pk1 pk2... pks каноническое разложение числа m, то сравнение (7) эквивалентно системе сравнений Пусть для каждого из сравнений системы (10) найдено решение тогда набор (a1, a2,..., as ) может быть единственным образом "поднят" до решения сравнения (7):

Пусть N число решений сравнения (7), а Ni число решений сравнения тогда N = N1 N2... Ns.

Поскольку каждое решение сравнения по примарному модулю является решением сравнения по простому модулю то для некоторого класса решений можно описать процедуру "поднятия" решения сравнения (12) до решения сравнения (11).

Определение. Назовем решение x a (mod p) сравнения (12) неособым, если f (a) не сравнимо с нулем по модулю p.

Сейчас мы покажем, что всякое неособое решение сравнения (12) единственным образом может быть "поднято" до решения сравнения (11). Достаточно описать переход от сравнения по модулю pk1 к сравнению по модулю pk.

Пусть x a (mod pk1 ) решение сравнения f (x) 0 (mod pk1 ).

Разложим f (x) по степеням x a:

(здесь b1 = f (a) не сравнимо с нулем по модулю pk1 ). Будем искать x в виде x = a + tpk1. После подстановки x в (13) получим откуда имеем Разделим получившееся сравнение вместе с модулем на pk1 :

(f (a), p) = 1, и найдем далее единственное t s (mod p). Полученный класс чисел определяет ровно один класс вычетов по модулю pk, который является решением сравнения (11).

Поясним процедуру "поднятия" на примере.

Задача. Найдите все решения сравнения x3 2 (mod 125).

Решение.

Первый шаг. Решим сравнение x3 2 (mod 5) методом испытаний полной системы вычетов. Нетрудно получить ответ x 3 (mod 5).

Второй шаг. "Поднимем" решение сравнения x3 2 (mod 5) до решения x3 2 (mod 25).

Положим x = 3+5t. Тогда f (x) = 3x2, f (3) 2 (mod 5), отсюда получим следовательно, x 3 (mod 25).

Третий шаг. Теперь поднимем решение x3 2 (mod 25) до решения исходного сравнения. Аналогично В итоге получаем ответ: x 53 (mod 125).

Определение. Назовем два сравнения по одному модулю эквивалентными, если множества решений этих сравнений совпадают.

Утверждение. Сравнение f (x) 0 (mod p), deg f (x) p, можно заменить эквивалентным степени, меньшей p.

Доказательство. Разделим f (x) на xp x с остатком:

где deg r(x) < p. Заметим, что в силу малой теоремы Ферма все классы вычетов по модулю p удовлетворяют сравнению Отсюда получаем, что сравнения f (x) 0 (mod p) и r(x) 0 (mod p) имеют одинаковые множества решений.

Задача. Решите сравнение Решение. Разделим многочлен f (x) на многочлен x5 x с остатком и перейдем к эквивалентному сравнению Задача. Докажите, что среди чисел, представимых многочленом положительной степени с целыми коэффициентами, имеется бесконечно много составных.

Решение. Пусть f (x) Z[x] многочлен степени n 1 с целыми коэффициентами, a целое число, не являющееся корнем f (x) и f (a) = 1.

Пусть f (a) = m. Многочлен f (x) не может принимать значение m более n раз.

Рассмотрим значения многочлена f (x) на последовательности bk = a+mk, k Z. По свойству I числовых сравнений из того, что bk a (mod m), следует Получаем, что последовательность f (bk ) состоит из чисел, кратных m. Так как каждое из чисел этой последовательности может появиться не более n раз, получаем, что среди f (bk ) бесконечно много составных.

Задача. Решите сравнения:

a) 7x4 + 19x + 25 0 (mod 27), b) 9x2 + 29x + 62 0 (mod 64).

14. Квадратичные вычеты. Символ Лежандра Определение. Пусть (a, m) = 1. Число a называется квадратичным вычетом по модулю m, если разрешимо сравнение x2 a (mod m), иначе число a называют квадратичным невычетом по модулю m.

Докажите следующие Утверждения.

1. Если m = p простое число, p > 2 и a квадратичный вычет по модулю p, то сравнение x a (mod p) имеет два решения.

Указание. Возведите в квадрат приведенную систему, состоящую из вычетов, наименьших по абсолютной величине.

2. В приведенной системе вычетов по модулю p поровну квадратичных вычетов и невычетов.

3. Произведение двух вычетов есть вычет, произведение двух невычетов вычет, а произведение вычета и невычета невычет.

4. Классы квадратичных вычетов образуют подгруппу индекса 2 в группе Z.

5. Число p 1 является квадратичным вычетом тогда и только тогда, Указание. Воспользоваться теоремой Вильсона и пунктом 3 предыдущего утверждения.

p делит a.

Справедлива следующая формула, принадлежащая Эйлеру:

Упражнение. Пользуясь формулой Эйлера, получите следующие свойства символа Лежандра:

Имеет место следующий красивый результат, принадлежащий Гауссу.

Теорема (квадратичный закон взаимности). Пусть p и q нечетные простые, тогда случае, когда Упражнение. Покажите, что Задачи 1. Среди вычетов приведенной системы по модулю 19 укажите квадратичные вычеты.

3. Пусть p 1 (mod 4). Докажите, что a и a одновременно являются или не являются квадратичными вычетами по модулю p.

4. Покажите, что число решений сравнения x2 a (mod p), где простое p не делит a, в точности равно 1 +.

5. Докажите, что где a пробегает полную систему вычетов по модулю p.

Разберем следующую задачу.

Задача. Используя квадратичный закон взаимности, вычислите символ Решение. Вычисления проведем, используя свойства символа Лежандра.

Заметим, что 195 94 (mod 101). Значит, Промежуточные результаты таковы:

Задачи 1. Используя свойства символа Лежандра, определите, сколько решений имеют сравнения:

3. Пусть 4. Укажите способ отыскания решений сравнения x2 a (mod p), где Указание. Покажите, что a(p1)/4 ±1 (mod p) и воспользуйтесь тем, 5. Докажите бесконечность множества простых чисел вида 1 + 4k.

Решение. Пусть простых чисел вида 1 + 4k конечное число и пусть все они занесены в список p1, p2,..., ps. Составим число 1 + 4p2 p2... p2.

Построенное число имеет простой делитель q, для которого Следовательно, q 1 (mod 4) и q число из указанного списка, чего быть не может.

6. Докажите бесконечность множества простых чисел вида 1 + 6k.

7. Найти арифметические прогрессии, в которых лежат простые p, для которых 3 квадратичный вычет.

8. Пользуясь теоремой Вильсона, доказать, что решениями сравнения 15. Символ Якоби Символ Якоби обобщает символ Лежандра на случай, когда знаменатель есть составное нечетное число.

Пусть m любое нечетное положительное число, m = p1 p2... ps каноническое разложение числа m на простые множители. (Здесь p1, p2,... ps не обязательно различны.) Тогда определим символ Якоби как произведеm ние символов Лежандра:

Для символа Якоби верны свойства 1 6 символа Лежандра и квадратичный закон взаимности.

Замечание. Для символа Якоби условие = 1 является необходимым, но не достаточным, чтобы сравнение имело решение.

Упражнение. Приведите пример не имеющего решений сравнения (14) такого, что символ Якоби m не равен 1.

Упражнение. Используя квадратичный закон взаимности, проверьте формулу Эйлера для n = 221 и a = 2.

Используя способы решения сравнений по примарному модулю, докажите следующее свойство.

Теорема. Пусть p нечетное простое, причем p не делит число a, тогда число N решений сравнения можно вычислить по формуле Если p = 2, то сравнение (15) разрешимо и имеет 4 решения при тогда и только тогда, когда 16. Порядки (показатели) вычетов и их свойства Пусть (a, m) = 1. Запишем теорему Эйлера:

Из сравнения следует, что существуют целые положительные числа k, удовлетворяющие условию Определение. Наименьшее из таких чисел называют показателем или порядком вычета a по модулю m.

Стандартно, если m фиксировано, порядок и показатель обозначают соответственно ord a (ordm a) и (a) (m (a)). Легко получить следующие свойства:

A. Если a b (mod m), то ord a = ord b.

B. Числа a0, a1, a2,..., ak1 различны по модулю m, где k = ord a.

C. Порядок вычета a следует искать среди делителей числа (m).

D. Если an 1 (mod n), то ord a делит n.

E. Если an as (mod n), то n s (mod k), где k = ord a.

F. Если n = p1 p2... ps, an 1 (mod m) и an/pi не сравнимо с 1 по модуs Приведем здесь доказательства свойств C и F.

Доказательство свойства C.

Пусть k = ord a. Разделим (m) на k с остатком:

Используя определение порядка и то, что r < k, заключаем, что r = 0.

Доказательство свойства F.

Поскольку k = ord a делитель числа n, то где 0 i i. Получаем, что число p1 p2... pi... ps делит n и не делит p1 p2... p i... ps. Следовательно, pi не делит pi, откуда i = i.

Упражнение. Докажите самостоятельно свойства A, B, D и E.

Задача 1. Докажите, что два числа Ферма Fn = 22 + 1 и Fm = 22 + 1, где m = n, взаимно просты.

Решение. Предположим, что n > m и p общий простой делитель чисел Fn и Fm. Тогда Получаем, что ordp 2 | 2m+1, следовательно, ordp 2 | 2n, но тогда Задача 2. Докажите, опираясь на свойства порядка, что Задача 3. Докажите, что если n = p1 p2... ps, an 1 (mod m) и для любого pi | n числа a не сравнимы с 1 по модулю m, то ordm a = n.

Задача 4. Пусть ordm a = k и ordm b = s, причем (k, s) = 1. Тогда ordm (ab) = ks.

Решение. Действительно, (a · b)ks 1 (mod m), следовательно, ord a · b делит k · s.

Пусть теперь p простой делитель k · s. Тогда, если p | k, то (p, s) = 1.

Рассмотрим Заметим, что aks/p не сравнимо с 1 по модулю m (см. задачу 2). Используя свойство F и задачу 3, получаем, что ord (a · b) делится на k · s.

Задача. Рассмотрим последовательность Пусть простое p не делит a · b. Найдите первый номер n, удовлетворяющий свойству 17. Первообразные корни и индексы Определение. Число a называется первообразным корнем по модулю m, если показатель (порядок) числа a по модулю m равен (m).

Упражнение. Составьте таблицы показателей для приведенной системы вычетов по модулю m. Проведите вычисления для m = 2, 4, 6, 7, 8, 9. Для каких из перечисленных модулей существуют первообразные корни?

Теорема (Гаусса). Первообразные корни существуют только для следующих модулей:

где p нечетное простое, целое положительное.

Доказать теорему Гаусса можно, реализовав следующий план:

A. Пусть f (x) многочлен степени n с целыми коэффициентами, среди которых не все кратны p. Тогда сравнение имеет не более чем n решений. Воспользуйтесь этим предложением для доказательства следующего факта:

многочлен xd 1, где d делитель числа p 1, имеет по модулю p ровно d корней.

Указание. Покажите, что справедливо сравнение и воспользуйтесь тем, что xp1 1 делится на xd 1 без остатка.

B. Пусть (l) количество вычетов в приведенной системе по модулю p, порядок которых равен l. Тогда и, в частности, Введем обозначения: F (d) = l|d (l) = d, где d делит p 1. Будем рассматривать F (n) как функцию на множестве целых положительных чисел, определенную условием C. Применим к равенству формулу обращения Мебиуса:

Итак, первообразный корень по модулю p существует, и число первообразных корней по модулю p равно (p 1).

D. Пусть g некоторый первообразный корень по модулю p. Если порядок g по модулю p2 не равен то рассмотрим число g · (p + 1). Заметим, что Чему равен показатель p + 1 по модулю p2 ?

Далее, пусть k и, следовательно, откуда следует, что p 1 делит k, то есть k = (p 1) · t и (p2 ) делится на k. Поскольку g не первообразный корень по модулю p2, то k = p1.

Окончательно получаем, что g · (p + 1) имеет порядок (p2 ).

E. Покажите, что любой первообразный корень g по модулю pk будет первообразным корнем и по модулю pk+1, где k 2. Примените метод математической индукции, используя следующие указания.

Покажите, что справедливы сравнения откуда следует, что Далее Используя свойство порядка F, получите нужный результат.

F. Докажите, что первообразным корнем по модулю 2p будет нечетный первообразный корень по модулю p.

G. Случаи m = 2 и m = 4 рассмотрите отдельно.

Как искать первообразные корни по модулю p? Запишем каноническое разложение числа p 1 = q1 1 q2 2... qs s, где qi различные простые.

Нам нужно подобрать такой вычет a, чтобы ordp a делился на qi i для любого i = 1, 2,..., s. Используя задачу 3, выпишем условие, определяющее первообразный корень по модулю p:

Методом испытаний найдем нужное a.

Замечание. Поскольку (p 1) число четное, то одно из условий системы будет выглядеть следующим образом:

или, что то же самое, Задача. Найдите наименьший первообразный корень по модулю 37.

Решение. Запишем систему, определяющую первообразный корень по модулю 37:

Заметим, что a первообразный корень по модулю 37 тогда и только тогда, когда Начнем с a = 2. Первое сравнение выполняется:

Проверим справедливость второго условия:

Таким образом, 2 наименьший первообразный корень по модулю 37.

корень по модулю p.

Степени первообразного корня образуют приведенную систему вычетов по модулю p. Для всякого целого a, взаимно простого с p, найдется число s такое, что 0 s p 2 и В этом случае показатель s называется индексом числа a по основанию g или дискретным логарифмом по модулю p. Для записи используют стандартное обозначение Поскольку p фиксированное число, то корректна и такая запись:

В качестве упражнения докажите следующие свойства индексов:

1. Если a b (mod p), то ind a = ind b.

Свойства индексов позволяют сводить решения степенных сравнений к решению линейных сравнений. Проиндексировать, или прологарифмировать, сравнение означает перейти к эквивалентному линейному относительно ind x сравнению Задачи 1. Укажите число первообразных корней и найдите наименьший первообразный корень по модулю p, если p = 23, 37, 97, 89.

2. Докажите, что первообразный корень простого числа q вида 2p + 1 при простом p вида 4n + 1 есть 2, а при p = 4n + 3 есть 2.

3. Докажите, что первообразный корень простого числа вида 4p + 1, где число p простое, есть 2.

4. Докажите, что первообразный корень простого числа вида 2n + 1, где 5. Расположите на окружности числа от 1 до 29 так, чтобы для трех чисел a, b, c, идущих подряд, выполнялось Сколькими способами это можно сделать?

6. Пусть p нечетное простое. Покажите, что для четного первообразного корня a по модулю p число a+p первообразный корень по модулю 2p.

7. Укажите необходимое и достаточное условие разрешимости степенного 8. Докажите, что для любого m, такого, что m делит число p 1, в Z существует ровно (m) чисел, порядок которых равен m.

9. Пусть p1, p2,..., ps нечетные простые числа. Докажите, что существует число a, являющееся одновременно первообразным корнем по каждому простому pi.

10. Обозначим через rn остатки от деления nn на p. Докажите, что последовательность rn периодическая. Найдите ее наименьший положительный период.

11. Известно, что a первообразный корень по модулю p. Что можно 12. Докажите, что классы квадратичных вычетов по модулю p образуют подгруппу в мультипликативной группе поля. Что можно выбрать в качестве образующей этой группы?

13. Найдя наименьший первообразный корень по модулю 23, получите все квадратичные вычеты по модулю 23.

первообразный корень по модулю pn. Покажите, что тогда 14. Пусть a a первообразный корень по модулю p.

Приведем решение следующей задачи.

Задача. Решите сравнение Решение. Выпишем условия, определяющие первообразный корень по Непосредственной подстановкой убеждаемся, что a = 2 первообразный корень по модулю 61. Проиндексируем сравнение Составим фрагмент таблицы индексов:

В итоге получим:

Заметим, что (7, 60) = 1, следовательно, сравнение имеет единственное решение:

Окончательно находим x:

Решением исходного сравнения является Задача. Найдите наименьший первообразный корень по модулю p, а также составьте фрагмент таблицы индексов, необходимый для решения сравнения:

1. 51x7 14 (mod 89), 2. 65x5 42 (mod 89), 3. 6x5 30 (mod 97), 4. 40x8 71 (mod 97), 5. 4x5 5 (mod 67), 6. 9x8 19 (mod 67), 7. 59x3 51 (mod 71), 8. 48x7 3 (mod 61), 9. 24x11 9 (mod 61), 10. 18x5 4 (mod 79), 11. 27x11 54 (mod 79), 12. 39x5 27 (mod 37), 13. 25x7 29 (mod 37).

Примерные варианты контрольной работы по курсу теории чисел Вариант 1. Решите систему сравнений 2. Решите сравнения 3. Найдите наименьший первообразный корень по модулю 47.

4. Решите сравнение 7x11 59 (mod 71).

Вариант 1. Решите систему сравнений 2. Решите сравнения 3. Найдите наименьший первообразный корень по модулю 59.

4. Решите сравнение 12x5 43 (mod 47).

Вариант 1. Решите систему сравнений 2. Решите сравнения 11x 37 (mod 59), 6x 18 (mod 27).

3. Найдите наименьший первообразный корень по модулю 79.

4. Решите сравнение 39x11 27 (mod 37).

Вариант 1. Решите систему сравнений 2. Решите сравнения 27x 9 (mod 18), 37x 1 (mod 18).

3. Найдите наименьший первообразный корень по модулю 37.

4. Решите сравнение 25x13 28 (mod 97).

Вариант 1. Решите систему сравнений 2. Решите сравнения 12x 4 (mod 16), 28x 7 (mod 19).

3. Найдите наименьший первообразный корень по модулю 31.

4. Решите сравнение 9x5 2 (mod 79).

Вариант 1. Решите систему сравнений 2. Решите сравнения 17x 24 (mod 37), 14x 21 (mod 35).

3. Найдите наименьший первообразный корень по модулю 29.

4. Решите сравнение 8x7 11 (mod 53).

Вариант 1. Решите систему сравнений 2. Решите сравнения 39x 18 (mod 42), 19x 7 (mod 23).

3. Найдите наименьший первообразный корень по модулю 79.

4. Решите сравнение 31x7 52 (mod 73).

Вариант 1. Решите систему сравнений 2. Решите сравнения 15x 37 (mod 97), 4x 14 (mod 26).

3. Найдите наименьший первообразный корень по модулю 83.

4. Решите сравнение 12x7 35 (mod 61).

Вариант 1. Решите систему сравнений 2. Решите сравнения 6x 33 (mod 39), 17x 61 (mod 37).

3. Найдите наименьший первообразный корень по модулю 67.

4. Решите сравнение 18x11 72 (mod 79).

Вариант 1. Решите систему сравнений 2. Решите сравнения 14x 28 (mod 49), 19x 3 (mod 71).

3. Найдите наименьший первообразный корень по модулю 59.

4. Решите сравнение 2x13 27 (mod 71).

Библиографический список [1] Cohen H. A Course in Computational Algebraic Number Theory. New York:

Springer-Verlag, 1996. 546 p.

[2] Ribenboim P. The New Book of Prime Number Records. New York: SpringerVerlag, 1996. 541 p.

[3] Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел. М.: Мир, 1987. 415 с.

[4] Виноградов И. М. Основы теории чисел. М.: Изд-во Лань, 2006. 176 c.

[5] Гашков С. Б., Чубариков В. Н. Арифметика. Алгоритмы. Сложность вычислений. М.: Изд-во Дрофа, 2005. 319 с.

[6] Коутинхо С. Введение в теорию чисел. Алгоритм RSA. М.: Постмаркет, 2001. 328 с.

[7] Серпинский В. 250 задач по элементарной теории чисел.

М.: Просвешение, 1968. 161 c.

Азовская Татьяна Владимировна Севостьянова Виктория Владимировна Компьютерная верстка, макет В. В. Севостьянова Подписано в печать 15.12.09. Формат 6084/16.

Бумага офсетная. Печать офсетная. Усл.-печ. л. 4,2. Уч.-изд. л. 4,5.

Typeset by L TEX. Тираж 150 экз. Заказ № Издательство Самарский университет ;

443011, Самара, ул. Академика Павлова, 1.