Сравнения, система вычетов, решение линейных систем по модулю
Будем рассматривать целые числа в связи с остатками от деления их на данное целое число m, которое назовем модулем. Каждому целому числу отвечает определенный остаток от деления его на m. Если двум целым a и b отвечает один и тот же остаток r, то они называются сравнимыми по модулю m.
Сравнимость для a и b записывается так :
[math]a \equiv b(mod \text < >m)[/math]
Сравнимость чисел a и b по модулю m равносильна:
- а. Возможности представить a в форме [math]\Huge[/math] , где t — целое.
- б. Делимости [math]\Huge[/math] на m.
- Действительно, из [math] a \equiv b(mod \text < >m) [/math] следует [math] a = mq + r, \text < >b = mq_1 + r [/math] , откуда [math] a — b = m(q-q_1)[/math] , и [math] a = b + mt[/math] , где [math] t = q — q_1[/math] .
- Обратно, из [math]\Huge[/math] , представляя b в форме [math] b = mq_1 + r [/math] , выводим [math] a = mq + r [/math] , где [math] q = q_1 + t [/math] , значит [math] a \equiv b(mod \text < >m) [/math] .
Арифметика сравнений
Свойства сравнений
- 1. Два числа, сравнимые с третьим сравнимы между собой. [math]a \equiv c(mod \text< >m) \text b \equiv c(mod \text< >m) \Rightarrow a \equiv b(mod \text< >m)[/math]
- Легко выводится из пункта «а».
- 2. Сравнения можно почленно складывать. [math] a_1 + a_2 + a_3 \equiv b_1 + b_2 + b_3(mod \text< >m)[/math]
- Представляем сравнения, как в пункте «а» и складываем.
- 3. Сравнения можно почленно перемножать. [math] a_1a_2a_3 \equiv b_1b_2b_3(mod \text< >m)[/math]
- Представляем сравнения, как в пункте «а», перемножаем, получим [math] a_1a_2a_3 = b_1b_2b_3+mN[/math] , где N—целое.
- 4. Обе части сравнения можно разделить на их общий делитель, если последний взаимно прост с модулем.
- Действительно, из [math]a \equiv b(mod \text < >m)[/math] , [math] a = a_1d, b = b_1d, (d,m)=1[/math] следует, что [math] a-b = (a_1 — b_1)d \vdots m [/math] , поэтому [math] a_1 \equiv b_1(mod \text < >m)[/math] .
- 5. Обе части сравнения можно умножить на одно и тоже число.
- Действительно, из [math]a \equiv b(mod \text < >m)[/math] , следует [math] a = b+mt, ak =bk +mkt [/math] , и, следовательно, [math]ak \equiv bk(mod \text < >mk)[/math] .
- 6. Обе части сравнения и модуль можно разделить на их общий делитель.
- Действительно, пусть [math]a \equiv b(mod \text < >m), a = a_1d, b=b_1d, m=m_1d[/math] , отсюда [math] a= b+mt, a_1d =b_1d +m_1dt, a_1 =b_1 +m_1t[/math] , и, следовательно, [math]a_1 \equiv b_1(mod \text < >m_1)[/math] .
- 7. Если сравнение [math]a\equiv b[/math] имеет место по нескольким модулям, то оно имеет место и по модулю равному НОК этих модулей.
- В самом деле, из [math] a \equiv b(mod \text< >m_1),\ldots,a \equiv b(mod \text< >m_k)[/math] следует, что разность [math] a-b [/math] делится на все модули [math] m_1,m_2,\ldots,m_k[/math] . Поэтому она должна делиться и на их НОК.
- 8. Если сравнение имеет место по модулю m, то оно имеет место и по модулю d, равному любому делителю числа m.
- Следует из пункта «б».
- 9. Если одна часть сравнения и модуль делятся на некоторое число, то и другая сторона сравнения должна делиться на это число.
- Следует из пункта «а».
- 10. Если [math]a \equiv b(mod \text< >m) [/math] , то [math](a,m) = (b,m) [/math] .
- Следует из пункта «а» по свойству НОДа.
Полная и приведенная система вычетов
Числа равноостаточные(сравнимые по модулю m) образуют класс чисел по модулю m. Из такого определения следует, что всем числам класса отвечает один остаток r, и мы получим все числа класса, если в форме [math]mt + r [/math] заставим t пробегать все целые числа. Таким образом для каждого значения остатка имеется свой класс чисел.
Любое число класса называется вычетом по модулю m. Вычет получаемый при [math] t = 0[/math] , равный самому остатку r, называется наименьшим неотрицательным вычетом.
Любые m чисел, попарно несравнимые по модулю m, образуют полную систему вычетов по этому модулю.
Согласно 10 свойству сравнений, числа одного класса по модулю m имеют одинаковый НОД. Особенно важны классы, содержащие числа, взаимно простые с модулем. Взяв вычет от каждого такого класса, получим приведенную систему вычетов по модулю m.
Решение линейных систем по модулю
Примеры решения
Пример 1.
[math] 12x \equiv 6(mod \text< >18)[/math]
Найдем НОД [math](12,18)=6 [/math]
Перейдем к новому сравнению [math] 2x \equiv 1(3) [/math]
Легко находится [math] x_0 = 2 [/math]
Тогда ответом будет [math] x_0 =2, x_1 = x_0 — \frac=-1, x_2 = -4[/math]Пример 2.
[math] 111x \equiv 75(mod \text< >321)[/math]
Найдем НОД [math](111,321)=3 [/math] , 75 кратно 3, значит имеем 3 решения
Перейдем к новому сравнению [math] 37x \equiv 25(107) [/math]
Воспользуемся цепными дробями, в нашем случае [math] n=4, p_ = 26[/math] , значит [math] x_0 \equiv -26\cdot 25 (107) \equiv 99(107) [/math]
Тогда ответом будет [math] x_0 = 99, x_1 = 206, x_2 = 313 [/math] .Сравнение по модулю натурального числа
Говорят, что два целых числа a и b сравнимы по модулю натурального числа n, если при делении на n они дают одинаковые остатки. Другими словами, a и b сравнимы по модулю n, если их разность a – b делится на n.
Пример: 32 и 39 сравнимы по модулю 7, так как 32 = 7∙4 + 4, 39 = 7∙5 + 4.
Утверждение a и b сравнимы по модулю n записывается в виде:
Отношение сравнения обладает многими свойствами обычных равенств. Например, если
a 1 ≡ b 1 ( mod n ) и a 2 ≡ b 2 ( mod n ) ,
a 1 a 2 ≡ b 1 b 2 ( mod n ) и a 1 + a 2 ≡ b 1 + b 2 ( mod n ) .
Классы вычетов [ ]
Множество всех чисел сравнимых с a по модулю n называется классом вычетов a по модулю n , и обычно обозначается [ a ] n или a ¯ n . Таким образом, сравнение a ≡ b ( mod n ) равносильно равенству классов вычетов [ a ] n = [ b ] n .
Сравнение по модулю n является отношением эквивалентности на множестве целых чисел Z > , и классы вычетов по модулю n представляют собой классы эквивалентности. Множество всех классов вычетов по модулю n обозначается Z n или Z / n Z /n\mathbb> .
[ a ] n + [ b ] n = [ a + b ] n [ a ] n ⋅ [ b ] n = [ a ⋅ b ] n
Относительно этих операций множество Z n является кольцом, а если n простое — полем.
Ссылки [ ]
- Виленкин Н. Я., Сравнения и классы вычетов, Квант, № 10, 1978.
- Виноградов И. М., Основы теории чисел, М.: ГИТТЛ, 1952.
- Сизый С. В., Лекции по теории чисел.
Научный форум dxdy
Последний раз редактировалось B@R5uk 15.01.2020, 00:02, всего редактировалось 4 раз(а).
Решил изучить как ведут себя остатки от деления квадратов и кубов в зависимости от модуля сравнения. Например, при сравнении по модулю 13 можно получить такую табличку:
x x^2 x^3
0 0 0
1 1 1
2 4 8
3 9 1
4 3 12
5 12 8
6 10 8
7 10 5
8 12 5
9 3 1
10 9 12
11 4 5
12 1 12Сразу видно, что у функции квадрат всегда есть повторяющиеся остатки, и, как следствие, отсутствующие остатки. Это, в принципе, очевидно: можно для каждого остатка рассмотреть дополнительный отрицательный остаток, после возведения в квадрат остатки с одинаковым модулем дадут один результат (кроме нуля и половины модуля, в случае, если он чётный).
С кубической функцией же результат немного интереснее. Иногда бывает так, что остатки куба пробегают все возможные значения остатков, и каждый остаток встречается только один раз без повторов и без пропусков. Например, табличка для остатков по модулю 10:
x x^2 x^3
0 0 0
1 1 1
2 4 8
3 9 7
4 6 4
5 5 5
6 6 6
7 9 3
8 4 2
9 1 9Сразу же хочется узнать, а что же это за числа, по модулю которых кубы дают все возможные остатки. Перебор в лоб дал такую вот последовательность до сотни:
2, 3, 5, 6, 10, 11, 15, 17, 22, 23, 29, 30, 33, 34, 41, 46, 47, 51, 53, 55, 58, 59, 66, 69, 71, 82, 83, 85, 87, 89, 94.
То, что в этой последовательности отсутствуют квадраты и вообще числа, в разложении которых на простые есть повторяющиеся множители, думаю, очевидно. Если модуль можно представить в виде , где при возведении в квадрат даст , которое делится на и, поэтому, даёт по модулю ноль. Ноль при умножении на снова даёт ноль, поэтому по крайней мере нулевой остаток у кубической функции повторяется.
С остальными отсутствующими в последовательности числами (среди которых есть и простые) не всё так просто. Так же анализируя разложение на простые множители, я обнаружил, что если модуль делится на простое число, которое даёт при делении на 3 остаток 1, то такой модуль в последовательность не входит. В результате, получается правило: последовательность состоит из чисел, в разложении которых на простые отсутствуют повторяющиеся множители И простые множители, сравнимые с 1 по модулю 3 (да, масло масленое: разложение модуля надо проверять по модулю). Проверка в лоб до , показало, что это правило выполняется.
Собственно вот мой вопрос: почему это так?
Re: Степени и сравнение по модулю
15.01.2020, 00:06Заслуженный участник Я занимался собственными «открытиями» на эту тему, а потом открыл для себя замечательную книжку
Дынкин, Успенский. Математические беседы.
(это тот самый Дынкин , ну и тот самый Успенский ).Очень советую! Кстати, половина текста книги находится в «Решениях» — сразу предупреждаю о таком стиле.
В частности, ответ на ваш вопрос там располагается в § 1.1.4, и в «решениях» к нему.
Re: Степени и сравнение по модулю
15.01.2020, 00:11Последний раз редактировалось B@R5uk 15.01.2020, 00:11, всего редактировалось 1 раз.
Munin , спасибо. Книжка есть вместе с полной коллекцией книжек математического кружка.
Скачал сто лет назад, но так и не добрался почитать.
Re: Степени и сравнение по модулю
15.01.2020, 00:13Заслуженный участник Вот она ровно про это (по крайней мере, её середина). О чём по названию нифига не догадаешься.
Re: Степени и сравнение по модулю
15.01.2020, 00:28
Munin в сообщении #1435232 писал(а):
половина текста книги находится в «Решениях» — сразу предупреждаю о таком стиле.Плохо, что ответы находятся в конце книги, а не сразу после задачи. Так же было бы более-менее сносным компромиссом, если решения были бы в конце параграфа.
Re: Степени и сравнение по модулю
15.01.2020, 00:57Заслуженный участник B@R5uk в сообщении #1435227 писал(а):
2, 3, 5, 6, 10, 11, 15, 17, 22, 23, 29, 30, 33, 34, 41, 46, 47, 51, 53, 55, 58, 59, 66, 69, 71, 82, 83, 85, 87, 89, 94.
Тут выписаны модули, по которым возможно только если .
По , к примеру, Значит эти кубы дадут одинаковые остатки при делении на , а опытов всего , и где-то образуются пробелы, то есть невычеты. Поэтому числа в списке нет.Re: Степени и сравнение по модулю
15.01.2020, 01:48Последний раз редактировалось B@R5uk 15.01.2020, 01:49, всего редактировалось 1 раз.
Andrey A , лучше говорить как в этой энциклопедии последовательностей : последовательность образуют такие числа , что уравнение разрешимо относительно для любых значений . То есть для любого натурального существует кубический корень по модулю.
Re: Степени и сравнение по модулю
15.01.2020, 02:39Заслуженный участник Ну, это как удобно. Важно, что в левых скобках разложения может оказаться любое число, а в правых — кратного пяти, к примеру, быть не может. И любому простому вида .
Re: Степени и сравнение по модулю
15.01.2020, 03:30Последний раз редактировалось B@R5uk 15.01.2020, 03:42, всего редактировалось 4 раз(а).
Munin , вроде чуть-чуть вникнул в доказательство теоремы в книжке.
Там используется (доказанный ранее) факт, что и p — простое. Далее, используя свойство деления в p -арифметике (видимо, тоже доказанное ранее), что деление 1 на x единственным образом сопоставляет x новое целое число y такое, что , показывают, что решение уравнения единственно и даёт , если . Для этого в (1) подставляется последнее равенство, получая: , где одна единица, потому что b должно быть в степени 1, когда записывают решение , а другая — из степени в малой теореме Ферма.
Однако, это всё описывает только частный случай. А именно: кубический корень по модулю M извлекается всегда, если , где p — простое. Это доказательство совершенно ничего не говорит, почему корень извлекается не всегда, если M делится на , но в то же время извлекается всегда, если M — составное из последовательности выше. Понятно, что общий случай как-то связан с частным, но как?
Andrey A в сообщении #1435262 писал(а):
Важно, что в левых скобках разложения может оказаться любое число, а в правых — кратного пяти, к примеру, быть не может .
Выделенное совершенно не понял. Можете пояснить развёрнутей, пожалуйста?
Re: Степени и сравнение по модулю
15.01.2020, 04:21Заслуженный участник Поясню. такое число нечетно и может содержать в каноническом разложении тройку и простые вида . По аналогии с числами вида (там двойка и простые вида ). Я намеренно избегаю терминологии, смотрите любой учебник по теории чисел.
Re: Степени и сравнение по модулю
15.01.2020, 08:54Заслуженный участник Последний раз редактировалось Sonic86 15.01.2020, 08:54, всего редактировалось 1 раз.
B@R5uk , ну детский сад, честное слово.
Если — простое число, то мультипликативная группа поля .
Если — циклическая группа порядка , то в ней уравнение имеет корней (для любого ).
Отсюда все следует в 2 счета.
Почитайте литературу, список тем с литературой в этом же разделе.Re: Степени и сравнение по модулю
15.01.2020, 13:56Заслуженный участник B@R5uk в сообщении #1435267 писал(а):
Это доказательство совершенно ничего не говорит, почему корень извлекается не всегда, если M делится на ,
Рассмотрите сначала, если
Sonic86 в сообщении #1435282 писал(а):
Если — простое число, то мультипликативная группа поля и со взаимной простотой
Re: Степени и сравнение по модулю
15.01.2020, 21:07Заслуженный участник Последний раз редактировалось Sonic86 15.01.2020, 21:14, всего редактировалось 1 раз.
Munin в сообщении #1435297 писал(а):
А где описан случай колец и со взаимной простотойЕсли брать множество взаимно простых с элементов из по умножению , то они образуют мультипликативную группу , не всегда циклическую. Сравнение при циклична при , а » — там про это написано.
Если же в сравнении не взаимно просто с , то там еще сложнее: будет полугруппой, ее граф будет типа ориентированного кольца с «хвостом, впадающим в кольцо». Численно для решения можно перебирать первые до тех пор, пока степени не попадут в «кольцо», после чего можно сократить общий множитель и вернуться к случаю группы . Китайская теорема об остатках тут тоже работает: конкретные сравнения вида . Тут я литературы не знаю кроме книги Ляпина Полугруппы.Модуль числа.
Модуль числа. Какие числа называются противоположными? Каким будет число, противоположное положительному числу? Отрицательному? Какое число противоположно самому себе? Сколько противоположных чисел имеет данное число? А сейчас я расскажу вам сказку, вы. Показать больше
Модуль числа. Какие числа называются противоположными? Каким будет число, противоположное положительному числу? Отрицательному? Какое число противоположно самому себе? Сколько противоположных чисел имеет данное число? А сейчас я расскажу вам сказку, вы послушайте и постарайтесь услышать слово, еще незнакомое вам. На числовой прямой собрались на совещание разные числа: положительное, отрицательное и Нуль. Он встал и стал держать речь: «Уважаемые числа, мы собрались здесь для того, чтобы оценить наши действия. Я должен отметить, хотя, может быть, это и не скромно, что от меня идет счет, поэтому я и буду давать вам оценку. Справа от меня находятся положительные числа, ничего отрицательного о них не скажешь. Слева – числа отрицательные. В жизни плохо быть отрицательным, но нам, в математике, часто не получить без них положительный ответ. Всякого одобрения заслуживает МОДУЛЬ, который всегда неотрицательный». Сидят числа и раздумывают: как понимать оценку Нуля? Какое новое слово вы узнали (м Спрятать
- Похожие публикации
- Поделиться
- Код вставки
- Добавить в избранное
- Комментарии