Введение в теорию сравнений по числовым модулям

Фирдман Илья Александрович

Лицей 533 Красногвардейского района Санкт-Петербурга

ВВЕДЕНИЕ В ТЕОРИЮ СРАВНЕНИЙ ПО ЧИСЛОВЫМ МОДУЛЯМ

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

1. Предварительные соображения

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

Напомним, что, как вы знаете из школьного курса, остатки от деления отрицательных чисел на положительные вычисляются по следующему принципу. Для чисел любого знака верно, что если a делится на dc остатком r (и неполное частное равно q), то a=d·q+r. По определению при этом остаток r неотрицателен и меньше, чем d. Этими условиями остаток определяется однозначно.

Например, 38=5·7+3 – значит, 38 делится на 5 с остатком 3 (неполное частное равно 7). -38=5·(-8)+2 – значит, -38 делится на 5 с остатком 2 (и неполным частным -8). Вообще, при изменении знака делимого остаток r заменяется на d-r – в нашем случае остаток 3 поменялся на 2=5-3.

При делении же целого числа на отрицательное остаток получается таким же, как при делении на его модуль: 38=(-5)·(-7)+3 – значит, остаток от деления 38 на (-5) равен 3.

Мы будем пользоваться также следующими леммами.

Лемма.Еслиa·b⋮c и (a,c) = 1, то b⋮c.(Напомним обозначения. Значок ⋮ означает «делится», то есть в условии леммы a·bделится на с. Скобками вида (a,c) обозначается НОД. Таким образом, лемма утверждает, что если a·b делится на cи НОД(a,c) = 1 (т.е. a и c взаимно просты), то bделится на c.

Доказательство. Разложим a,bиc на простые множители. Из условия следует, что aиc не имеют общих множителей – значит, все простые множители cдолжны содержаться в b, что и требовалось.

Лемма.Еслиa⋮b,a⋮cи (b,c)=1, то a⋮bc.

Доказательство.Из условия следует, что a включает в себя все простые множители, содержащиеся в b и в c,в нужных степенях.

Замечание.Еслиbиcне взаимно просты, то a может не делиться на их произведение. Например, 12 ⋮ 6, 12 ⋮ 4, но12 не делится на 24. Причина в том, что 6 и 4 содержат общий множитель 2, которых в разложении 12 на простые множители встречается только один раз. Взаимная простота bиc исключает такую ситуацию.

2. Сравнения

Определение. Говорят, что целые числа a и b сравнимы по целому ненулевому модулюm, если они имеют одинаковые остатки по этому модулю. При этом пишут a≡b (modm)или.

Например, 12 ≡ 27 (mod 5), 12 ≡ 2 (mod 5), 10 ≡ 22 (mod 3), 10 ≡ -2 (mod 3), 12 ≡ 27 (mod -5).

Сравнимость бывает удобно проверять при помощи следующего критерия

Критерий сравнимости.a≡b (modm) тогда и только тогда, когда a-b⋮m. (напомним, что значок ⋮ означает «делится», то есть a≡b (modm) тогда и только тогда, когда a-b делится на m).

Доказательство. Если a≡b (modm), то aиbимеют одинаковые остатки при делении на m. Поэтому остаток их разности при делении на m будет равен нулю, что и требовалось. Обратно, если a-b⋮m, то разность их остатков при делении наm равно 0 – значит, эти остатки равны.

Замечание. Из критерия следует, что a≡b (modm)равносильно тому, что a=b+mqдля некоторого целого q. (q=(a-b)/m).

К обоим частям сравнения одновременно можно прибавить, вычесть или домножить их на одно и то же число, и оно по прежнему будет выполняться (как и обычное равенство). Сравнения по одному модулю можно складывать, вычитать или умножать друг на друга, как обычные равенства (при этом модуль сравнения остается прежним). Наконец, обе части сравнения можно возвести в одну и ту же натуральную степень. Все это следует из известных нам правил работы с остатками – остаток в левой части будет при этих операциях меняться так же, как и остаток в правой части.

Примеры. 1) Из сравнения 5 ≡ 17 (mod 3) следует, что 1005 ≡ 1017 (mod 3).

2) Из перемножения сравнений 7 ≡ 12 (mod 5) и 8 ≡ 3 (mod 5) следует, что 56 ≡ 36 (mod 5).

3) Из сравнения 20 ≡ -1 (mod 7) следует, что 8000=20³ ≡ -1 ≡ 6 (mod 7), а 20¹⁰⁰ ≡ 1 (mod 7).

Упражнение 1. Найдите остаток от деления числа 123456789012345678901234567890⁵³³ на 123456789012345678901234567891.

3. Сокращение сравнений на множитель

Поскольку делить остатки друг на друга в общем случае нельзя, то не всегда можно и делить друг на друга сравнения (или даже делить обе части сравнения на одно число).

Пример. Сравнение 20 ≡ 14 (mod 6) нельзя сократить на 2 – полученное в результате сравнение 10 ≡ 7 (mod 6) неверно.

В действительности, если d – общий делитель a,b и m, то из сравнения a≡b (modm) следует a/d≡b/d (modm/d). Действительно, как было показано выше,a≡b (modm) равносильно a=b+mq для некоторого целого q. Тогда (a/d)=(b/d)+(m/d)q, откуда и следует требуемое.

Пример.Из сравнения 20 ≡ 14 (mod 6) следует верное сравнение 10 ≡ 7 (mod 3).

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

Теорема (о сокращении в сравнениях). Пустьa≡ b (mod m).Пустьd является общим делителем a и b, и при этом d и m взаимно просты. Тогда a/d≡b/d (modm).

Доказательство.По критерию сравнимости a-b⋮m, то есть a-b=mqдля некоторого целого q, Поскольку a и b делятся на d, на d делится и их разность, равная mq. А раз m взаимно просто с d, то на d делится q. Тогда a/d – b/d = m·(q/d), откуда следует, что a/d – b/d⋮m, что по критерию сравнимости и доказывает требуемое.

4. Малая теорема Ферма

Теперь мы можем доказать следующую важную теорему.

Теорема (малая теорема Ферма). Пусть p – простое, a не делится на p. Тогда a^p-1≡1 (modp).

Следствие. Пустьp – простое, a любое целое. Тогдаa^p≡a (mod p). (Для доказательства достаточно домножить обе части сравнения из теоремы на a; случай a⋮p, в котором теорема неприменима, дает 0 в обеих частях сравнения).

Пример. Любое число при возведении в 5-ю степень сохраняет остаток от деления на 5. Это можно проверить, возведя в 5-ю степень все возможные остатки.

Доказательство теоремы. Рассмотрим набор из p-1остатков от деления на p следующих чисел: a,2a,3a, …, (p-1)a. Все эти остатки различны, поскольку если какие либо два равны: ma≡na(modp), то, в силу взаимной простоты aиp, мы можем сократить это сравнение до m≡n(modp), что невозможно при 1≤m,n≤p-1. Значит, мы имеем дело с полным набором остатков 0,1,2,…,p-1, лишь записанным в другом порядке.

(Например, если p=5,a=2, мы получим следующий набор чисел: 2, 2·2, 3·2, 4·2, дающих остатки 2, 4, 1, 3 при делении на 5 – то есть 1, 2, 3, 4 в другом порядке).

Тогда перемножить остатки от деления чиселa,2a,3a, …, (p-1)a на p суть то же самое, то перемножить остатки 1, 2, 3, …, (p-1) – от перестановки сомножителей произведение не изменится. Поэтому

a·2a·3a·…·(p-1)a≡1·2·3·…·(p-1) (modp).

Преобразуем левую часть этого сравнения, собрав вместе все a:

a^p-1·1·2·3·…·(p-1) ≡1·2·3·…·(p-1) (modp).

Поскольку произведение 1·2·3·…·(p-1)взаимно просто с p, мы можем сократить на него обе части сравнения, окончательно получая a^p-1≡1 (modp), что и требовалось.

Упражнение 2. Найдите остаток от деления 2¹⁰⁰ на 97.

Упражнение 3.Пустьp>5 – простое число. Докажите, что число 111…11, состоящее из p-1 единиц, делится на p.

5. Функция Эйлера и теорема Эйлера

Для обобщения малой теоремы Ферма на остатки по составному модулю понадобится следующее понятие.

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

Примеры.1) φ(10)=4. Среди натуральных чисел, меньших 10, взаимно просты с 10 только 4 числа: 1, 3, 7, 9.

2) Пусть p – простое. Тогда φ(p)=p-1. Действительно, в силу простоты p с ним будут взаимно просты все числа, меньшие его.

Упражнение 4. Не ссылаясь на приведенную ниже теорему, докажите, что для натуральной степени простого числа φ(pⁿ) =pⁿ - p^n-1.

Теорема.Пусть натуральное число n раскладывается на простые множителиp₁,p₂, …, p_k следующим образом:

.

Тогда

Упражнение 5.Докажите второе из равенств в этой формуле.

Пример.φ(24)= φ(2³·3²)=24·(1 - 1/2)·(1 – 1/3)=24 · 1/2 · 2/3 = 8.

Упражнение 6.Найдите φ(240).

Обобщение малой теоремы Ферма на составные модули формулируется так.

Теорема (Эйлера). Пусть n – натуральное, a– целое, такое, что (a,n)=1. Тогда a^φ(n)≡ 1 (modn).

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

Упражнение 7.а) Пользуясь теоремой Эйлера, докажите, что сравнение x·a≡1 (modn) всегда имеет решение, если (a,n)=1 (aиn даны, неизвестной является x).

б) Докажите то же самое для сравнения x·a≡b (modn) при произвольном b.

6. Китайская теорема об остатках

Суть китайской теоремы об остатках состоит в том, что если есть набор каких-либо попарно взаимно простых модулей, то всегда можно найти число, дающее по всем этим модулям любые заданные остатки. Например, существует число, дающее остаток 2 по модулю 7, одновременно с этим остаток 9 по модулю 15 и остаток 0 по модулю 4. Сформулируем и докажем эту теорему на языке сравнений.

Теорема (китайская теорема об остатках)

Пустьm₁,m₂, …, m_k – попарно взаимно простые числа (каждое взаимно просто с каждым), r₁,r₂, …, r_k– произвольные целые числа. Тогда система сравнений

имеет ровно одно решение в интервале 0≤x<m₁m₂·…·m_k.

Доказательство. Сначала покажем, что в заданном интервале существует не более одного решения. Действительно, если бы существовали два решения x и x’, то они были бы сравнимы по всем модулямm₁,m₂, …, m_k,и тогда по критерию сравнимости их разность делилась бы на все эти взаимно простые модули – а значит, и на их произведение. Но разность любых двух чисел из указанного интервала меньше, чем m₁m₂·…·m_k.

Теперь докажем существование решения. Пусть решения не существует. Попробуем поменять остатки в правой части сравнений. Заметим, что для каждого возможного набора остатков r₁,r₂, …, r_k может существовать, как было показано выше, не более одного решения системы сравнений в интервале 0≤x<m₁m₂·…·m_k. Рассматривая все возможные наборы остатков (которых будет m₁m₂·…·m_k – m₁вариантов остатка r₁,m₂ варианта остатка r₂ и т.д), мы получим тогда менее, чемm₁m₂·…·m_k решений различных систем сравнений (какая-то из m₁m₂·…·m_k систем сравнений, по нашему предположению, не имеет решения), лежащих в нашем интервале. Поскольку интервал содержит ровно m₁m₂·…·m_k чисел (от 0 до m₁m₂·…·m_k- 1), какое-то из чисел не будет удовлетворять ни одной из рассмотренных систем сравнений. Но такое невозможно – для любого числа можно xпостроить истинную систему сравнений, просто взяв в качестве r₁,r₂, …, r_k его остатки от деления на m₁,m₂, …, m_k. Противоречие.

Пример. Система сравнений

имеет решение x=324. Это решение единственно в интервале 0≤x<420=7·15·4. Прочие решения сравнения имеют вид 324+420n для произвольных целых n. (Очевидно, что при прибавлении к x числа, кратного 420, его остатки по модулям 7, 15, 4 не изменяются).

Упражнение 8.Приведите пример системы из двух сравнений по различным, но не взаимно простым модулямm₁,m₂, не имеющую решений. Обоснуйте отсутствие у нее решений.

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

1. Дано целое число Х. Каким может быть количество чисел от -100 до 100, сравнимых с Х по модулю 67?

2. Найдите такое число Y, что 5Y ≡ 8 (mod 11).

3. а) Найдите остаток от деления 12⁵³³ на 13.

б) Докажите, что 30⁹⁹+23¹⁰¹ делится на 66.

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

5*. Докажите, что 1ⁿ+2ⁿ+…+(n-1)ⁿ делится на n при нечетном n.

6*. Пусть n – натуральное число, такое, что n+1 делится на 24. Докажите, что тогда сумма всех натуральных делителей n делится на 24.

7. Докажите, что 4135⁵³³+ 3241⁵³³делится на 7376.

8. а) Найдите остаток от деления 7¹⁶¹⁶¹ на17.

б) Докажите, что 13¹⁰⁸ – 1 делится на 95.

9*. Пусть p>5 – простое число. Докажите, что число 111…11 (из p-1 единицы) делится на p.

10*. Пусть p – простое число, и А не делится на p. Докажите, что всегда можно «разделить» 1 на А по модулю p: найти такое число Х, что А·Х ≡ 1 (modp).

11. Пусть p,q – простые числа. Пользуясь только определением, выразите φ(p²q) через p и q.

12. Найти X, удовлетворяющий сравнениям X ≡ 2 (mod 8), X ≡ 6 (mod 11), X ≡ 3 (mod 13).

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

а)X ≡ 2 (mod 6), X ≡ 7 (mod 15).

б)X ≡ 23 (mod 26), X ≡ 13 (mod 28).

Использованная литература

1. С.А. Генкин, И.В. Итенберг, Д.В. Фомин. Ленинградские математические кружки. Киров: 1994.

Адрес публикации: https://www.prodlenka.org/metodicheskie-razrabotki/266019-vvedenie-v-teoriju-sravnenij-po-chislovym-mod