Как найти сравнимое по модулю число - Исправление недочетов и поиск решений вместе с Examum.ru

1.2 Теория сравнений и ее приложения

1.2.1 Сравнение по модулю

Определение 1.11 Числа, дающие при делении на m одинаковые остатки, называются сравнимыми по модулю . Обозначение: .

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

Итак, если два целых числа и сравнимы по модулю , то этот факт можно записать разными способами: или a=b+mk , где — целое число, или a-b=mk или .

Далее, если a=mq+r , то есть при делении на дает остаток , то a-r=mq или . Таким образом, любое целое число всегда сравнимо с остатком , получающимся при делении его на .

Свойства сравнений, не зависящие от модуля

Отношение сравнимости удовлетворяет условиям:

Отношение, заданное на множестве и обладающее перечисленными свойствами, задает разбиение этого множества на непересекающиеся классы. Применительно к отношению сравнимости по модулю это означает: все множество целых чисел разбивается на классы чисел, эти классы не пересекаются. Так, есть класс нуля: это все числа, сравнимые с нулем по модулю ,то есть делящиеся на без остатка(включая и само число 0), класс единицы — все числа, дающие остаток 1 при делении на , класс 2, …,класс m-1 . Например, пусть m=5 . Получаем следующие классы:

$begin{array}{lcl} bar{0}&=&{dots,-10, -5, 0, 5, 10, 15, 20,dots} \[1ex] bar{1}&=&{dots,-9, -4, 1, 6, 11, 16, 21,{dots}} \[1ex] bar{2}&=&{dots,-8, -3, 2, 7, 12, 17, 22,{dots}} \[1ex] bar{3}&=&{{dots},-7, -2, 3, 8, 13, 18, 23,{dots}} \[1ex] bar{4}&=&{{dots},-6, -1, 4, 9, 14, 19, 24,{dots}}. end{array}$

(
1.2)

Определение 1.12 Классы (1.2) называются классами вычетов.

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

Следствие 1.6 Члены сравнения можно переносить из одной части сравнения в другую с противоположным знаком.
Сравнения по одному и тому же модулю можно почленно перемножать.

Следствие 1.7 Обе части сравнения можно возводить в одну и ту же целую неотрицательную степень: если и — целое неотрицательное число, то .
Обе части сравнения можно умножать на одно и то же целое число.

Свойства сравнений, зависящие от модуля

Если и , то .
Обе части сравнения и модуль можно умножить на одно и то же целое положительное число.
Если и , то $a equiv b mod {frac{m}{d}}$ .

Приведем следствия из свойства 9.

Следствие 1.8 Если , т. е. если , то из следует $a equiv b mod frac{m}{k}$ , а это означает, что обе части сравнения и модуль можно разделить на любой их общий делитель.

Большое значение имеет

Следствие 1.9 Если , т. е. если , то из следует , а это означает, что обе части сравнения можно разделить на их общий делитель, если он взаимно прост с модулем.

Пример 1.9 .

После деления обеих частей сравнения на получим .

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

Пример 1.10 , но .
Если сравнение имеет место по нескольким разным модулям, то оно имеет место и по модулю, равному наименьшему общему кратному этих модулей.
Из рассмотренных свойств сравнений вытекает следующее общее свойство.
Пусть — многочлен с целыми коэффициентами, и — переменные, принимающие целые значения. Тогда если , то .

Если и , то

$c_na^n+c_{n-1}a^{n-1}+ldots+c_1a + c_0 = d_nb^n + d_{n-1}b^{n-1}+ldots+d_1b + d_0 ~(mod m).$

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

Вместе с тем следует обратить внимание на то, что встречающиеся в сравнениях показатели степеней заменять таким образом нельзя: из $a^{n} equiv c~(mod m)$ и не следует, что $a^{k} equiv c~(mod m)$ .

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

Пример 1.11 Доказать, что при любом натуральном число $37^{n+2} + 16^{n+1} +23^{n }$ делится на .

Решение. Очевидно, что , , .

Возведем первое сравнение в степень , второе — в степень , третье — в степень . Полученные сравнения: $37^{n+2} equiv 2^{n+2}~(mod 7)$ , $16^{n+1} equiv 2^{n+1}~(mod 7)$ , $23^{n} equiv 2^{n}~(mod 7)$ , сложим:

$37^{n+2} +16^{n+1} +23^{n } equiv 2^{n} cdot (2^{2}+2^{1}+1) ~(mod 7) equiv 2^{n}cdot 7~(mod 7)$ , то есть $37^{n+2} +16^{n+1} +23^{n}$ делится на .

Пример 1.12 Найти остаток от деления числа $(9674^{6} +28)^{15}$ на .

Решение. Так как , то $9674^{6} equiv 2^{6}~(mod 39)=64 equiv 25~(mod 39)$ . Далее, . Следовательно, $(9674^{6} +28)^{15}equiv 14^{15}$ . И задача теперь сведена к следующей: найти остаток от деления $14^{15}$ на . Воспользуемся сравнениями: и . Из следует: $14^{14}equiv 1~(mod 3)$ . А из сравнения следует: $14^{14}equiv 1~(mod 13)$ . И так как сравнение имеет место по модулям и , то оно имеет место и по модулю , являющемуся НОК чисел и . Итак, $14^{14}equiv 1~(mod 39)$ . Но в таком случае $14^{15}equiv 14~(mod 39)$ .

1.2.2 Возведение в степень по модулю

Пусть , нам необходимо вычислить . В дальнейшем перед нами часто будет стоять такая задача с очень большими числами , , . Очевиднейший способ вычислить — вычислить произведение $underbrace{acdot acdots a}_{n text{раз}}$ и взять остаток от деления на . Для этого потребуется умножений и взятие остатка от деления огромного числа (не всегда даже его хранение в памяти может быть простым) по модулю . Приведём оптимизации для этой задачи.

Из свойства

следует, что промежуточные результаты вычислений можно перед хранением брать по модулю .
Сгруппируем сомножители в произведении особым образом. Пусть , $b_iin{0,1}$ . Имеем:

$a^b ~(mod m) = a^{b_0} cdot (a^2)^{b_1} cdot (a^4)^{b_2} cdots left(a^{(2^n)}right)^{b_n} ~(mod m).$

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

$2^n b_n + 2^{n-1} b_{n-1} + ldots + 2 cdot b_1 + b_0 ~~rightarrow~~ 2^{n-1} b_{n} + ldots + 2 cdot b_2 + b_1.$

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

Пункт 2 даёт следующий алгоритм возведения в степень по модулю.

Вход: , , — целые неотрицательные числа.

Выход: — результат возведения в степень по модулю .

Также отметим, что на шаге 1 копирование b'=b , x=a выполняются для того, чтобы не испортить значения , , которые могут передаваться в наш алгоритм по указателю или ссылке.

Источник

Алгебра и начала математического анализа, 10 класс

Урок №8. Сравнения.

Перечень вопросов, рассматриваемых в теме

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

Глоссарий по теме

Определение. Если а и b — два целых числа и их разность а — b делится на натуральное число m, то говорят, что a и b сравнимы по модулю m.

Свойства сравнений:

a ≡ b (mod m), b ≡ c (mod m), a ≡ c (mod m)
a ≡ b (mod m) b ≡ a (mod m)
a₁ ≡ b₁ (mod m), a₂ ≡ b₂ (mod m), … , a_k ≡ b_k (mod m) a₁+…+a_k≡ b₁+…b_k(mod m)
a+b ≡ c (mod m) a ≡ c–b (mod m)
a ≡ b (mod m) a+mt ≡ b+mk(mod m) (t, k ∈ Z)
a ≡ b (mod m), c ≡ d (mod m) ac ≡ bd (mod m)
a ≡ b (mod m) a^k ≡ b^k(mod m)
a ≡ b (mod m) ak ≡ bk(mod m)
Если a ≡ b (mod m), (a, b) = c, (c, m) = 1 (mod m)
a ≡ b (mod m) ak ≡ bk (mod mk)
a ≡ b (mod m), a = a₁d, b = b₁d, m = m₁d a₁ ≡ b₁(mod m₁)
a ≡ b (mod m₁), a ≡ b(mod m₂), …, a ≡ b(mod m_k) a ≡ b (mod НОК(m₁,…,m_k))
a ≡ b (mod m), d/m a ≡ b(mod d)
d/a, d/m, a ≡ b(mod m) d/b
a ≡ b (mod m) (a, m) = (b, m)

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

Теорема 1. Если , то сравнение (7) имеет единственное решение.

Теорема 2. Если и число bне делится на d , то сравнение ax ≡ b (mod m) не имеет решений.

Теорема 3. Если и , b ≡ d то сравнение (7) имеет d решений.

Основная литература:

Колягин Ю.М., Ткачева М.В, Федорова Н.Е. и др., под ред. Жижченко А.Б. Алгебра и начала математического анализа (базовый и профильный уровни) 10 кл. – М.: Просвещение, 2014.

Дополнительная литература:

Шабунин М.И., Ткачева М.В., Федорова Н.Е. Дидактические материалы Алгебра и начала математического анализа (базовый и профильный уровни) 10 кл. – М.: Просвещение, 2017.

Теоретический материал для самостоятельного изучения

Два целых числа, разность которых кратна данному натуральному числу m, называются сравнимыми по модулю m. (Слово «модуль» происходит от латинского modulus, что по-русски означает «мера», «величина».) Утверждение «a сравнимо с b по модулю m» обычно записывают в виде a ≡ b (mod m), и называют сравнением. Вот примеры сравнений: 5 ≡ 1 (mod 2), 48 ≡ 0 (mod 6), 16 ≡ 9 (mod 5). Сравнение по модулю 1 выполняется для любых двух целых чисел, так как всякое число кратно 1. Два числа сравнимы по модулю 2, если они одной четности, т.е. либо оба четны, либо оба нечетны.

Определение сравнения было сформулировано в книге К. Ф. Гаусса «Арифметические исследования». Эту работу, написанную на латинском языке, начали печатать в 1797 г., но книга вышла в свет лишь в 1801 г. из-за того, что процесс книгопечатания в то время был чрезвычайно трудоемким и длительным. Первый раздел книги Гаусса так и называется: «О сравнении чисел вообще».

Сравнениями очень удобно пользоваться в тех случаях, когда достаточно знать в каких-либо исследованиях числа с точностью до кратных некоторого числа. Например, если нас интересует, на какую цифру оканчивается куб целого числа a, то нам достаточно знать a лишь с точностью до кратных числа 10, и можно пользоваться сравнениями по модулю 10.

Определение сравнений.

Мы выражаем это записью

a ≡ b (mod m), (1)

которая читается так: а сравнимо с b по модулю m.

Делитель m мы предполагаем натуральным; он называется модулем сравнения. Наше высказывание (1) означает, что

a — b = mk, где k — целое число. (2)

Пример 1.

1) 23 ≡ 8 (mod 5), так как 23 — 8 = 15 = 5 ∙ 3;

2) 47 ≡ 11 (mod 9), так как 47–11 = 36 = 9 ∙ 4;

3) —11 ≡ 5 (mod 8), так как — 11 — 5 = —16 = 8 ∙ (-2);

4) 81 ≡ 0 (mod 27), так как 81 — 0 = 81 = 27 ∙ 3.

Последний пример показывает, что вообще, вместо того, чтобы говорить: число а делится на число m, мы можем записать a ≡ 0 (mod m), так как это означает, что а — 0 = а = mk, где k — некоторое целое число.

Например, вместо того, чтобы сказать, что а — четное число, мы можем записать a ≡ 0 (mod 2).

Таким же образом видно, что нечетное число является числом, удовлетворяющим сравнению а ≡ 1 (mod 2).

Обобщим свойства сравнений:

a ≡ b (mod m), b ≡ c (mod m), a ≡ c (mod m)
a ≡ b (mod m) b ≡ a (mod m)
a₁ ≡ b₁ (mod m), a₂ ≡ b₂ (mod m), … , a_k ≡ b_k (mod m) => a₁+…+a_k≡ b₁+…b_k(mod m)
a+b ≡ c (mod m) a ≡ c–b (mod m)
a ≡ b (mod m) a+mt ≡ b+mk(mod m) (t, k ∈ Z)
a ≡ b (mod m), c ≡ d (mod m) ac ≡ bd (mod m)
a ≡ b (mod m) a^k ≡ b^k(mod m)
a ≡ b (mod m) ak ≡ bk(mod m)
Если a ≡ b (mod m), (a, b) = c, (c, m) = 1 (mod m)
a ≡ b (mod m) ak ≡ bk (mod mk)
a ≡ b (mod m), a = a₁d, b = b₁d, m = m₁d a₁ ≡ b₁(mod m₁)
a ≡ b (mod m₁), a ≡ b(mod m₂), …, a ≡ b(mod m_k) a ≡ b (mod НОК(m₁,…,m_k))
a ≡ b (mod m), d/m a ≡ b(mod d)
d/a, d/m, a ≡ b(mod m) d/b
a ≡ b (mod m) (a, m) = (b, m)

Нахождение обратного элемента

Задача нахождения обратного элемента: найти b=a^-1 (mod n), где a и n заданы, b неизвестно.

Элемент b называется обратным к a по модулю n, если a∙b≡1(mod n). Тогда пишут, что b ≡ a^–1 (mod n). Справедлива

Теорема обратимости:

Существует a^-1 (mod n) (a, n) = 1.

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

Найти обратный элемент можно с помощью расширенного алгоритма Евклида:

Пусть a > n; a, Расширенный алгоритм Евклида находит числа x, y: ax+ny = НОД(a, n).

Вычисляет цепочка равенств:

a = nq1 + r1;

n = r1q2 + r2;

r1 = r2q3 + r3;

…..

rk−2 = rk-1qk + rk;

rk−1 = rkqk+1.

Используя эту цепочку, восстанавливаем:

r_k = r_k-2 – r_k-1q_k= r_k-2 – (r_k-3 – r_k-2q_k-1)q_k = … =ax+ny.

Получаем сравнение ax+ny≡1(mod n). Поскольку ny≡0(mod n), то ax≡1(mod n), а значит полученное с помощью расширенного алгоритма Евклида число x как раз и есть искомый обратный элемент к числу a по модулю n.

Пример 2.

Вычислить элемент, обратный а по mod n, если a=9; n=29;

Решение:

Воспользуемся расширенным алгоритмом Евклида:

29=9∙3+2

9=2∙4+1

2=1∙2+0

Обратный ход:

1=9-2∙4=9∙1-(29-9∙3)∙4=9∙13-29∙4.

Проверка:

13∙9=117. 117≡1(mod( 29)).

Ответ: обратный элемент = 13.

Сравнения первой степени

Сравнения первой степени имеют вид

a₁x+a₀≡0 (mod m) (6).

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

ax≡ b (mod m) (7)

При решении таких сравнений рассматривают два случая:

и .

Теорема 1. Если , то сравнение (7) имеет единственное решение.

Теорема 2. Если и число b не делится на d, то сравнение ax≡ b (mod m) не имеет решений.

Теорема 3. Если и b ≡ d, то сравнение (7) имеет d решений.

Решение сравнений первой степени

Рассмотрим 2 способа решения сравнений первой степени, в основе которых лежит приведение сравнения первой степени к равносильному сравнению с коэффициентом при x , равному единице.

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

Решить сравнение 25х≡15(mod 17)

1 способ

2 способ

НОД(25,17)=1

Значит сравнение имеет единственное решение.

25х≡15 (mod 17)

5х≡3 (mod 17)

5х≡3+17 (mod 17)

5х≡20 (mod 17)

х≡4 (mod 17)

НОД(25,17)=1

Значит сравнение имеет единственное решение.

25х≡15 (mod 17)

5х≡3 (mod 17)

Найдем обратный элемент к 5, используя алгоритм Евклида:

17=5∙3+2

5=2∙2+1

2=2∙1+0

1=5 – 2∙2 = 5 – 2 ∙ (17 – 5∙3) = 5∙7 – 17∙2

таким образом обратным для 5 по модулю 17 будет 7.

5х≡3 (mod 17)

7∙5х ≡ 7∙3 (mod 17)

х ≡ 21 ≡ 4 (mod 17)

Разбор решения заданий тренировочного модуля

№1. Тип задания: выбор элемента из выпадающего списка

Решите сравнение 21х≡13 (mod 7)

Выпадающий список:

Решим данное сравнение:

Наибольший общий делитель

a=25 и m=7:

d=NOD(25,7)=1

Так как b:d=10:1=10 целое, то, следовательно, сравнение имеет d=1 решений по модулю m= 7.

Числа, удовлетворяющие сравнению:

x=7t+6 (t∈Z).

Решение сравнения:

x≡6(mod7).

Верный ответ 4. 6

№2. Тип задания: ввод с клавиатуры пропущенных элементов в тексте.

Вычислить элемент, обратный а по mod n, если a=7; n=17

Обратный элемент_____

Решим данное задание:

Воспользуемся расширенным алгоритмом Евклида:

17=7∙2+1

7=2∙3+1

2=1∙2+0

Обратный ход:

1=7-2∙3=7∙1-(17-7∙2)∙2=7∙5-17∙2.

Проверка:

5∙7=35. 35≡1(mod( 17)).

Ответ:

Обратный элемент 5.

Источник

Сравне́ние двух целых чисел по мо́дулю натурального числа — математическая операция, позволяющая ответить на вопрос о том, дают ли два выбранных целых числа при делении на один и тот же остаток. Любое целое число при делении на дает один из возможных остатков: число от 0 до m-1 ; это значит, что все целые числа можно разделить на групп, каждая из которых отвечает определённому остатку от деления на .

Мо́дульная арифме́тика, часто называемая модуля́рной арифметикой^[1]^[2], широко применяется в математике, информатике и криптографии^[3].

Содержание

1 История
2 Определения
3 Свойства сравнимости по модулю
4 Операции со сравнениями
- 4.1 Пример
5 Связанные определения
- 5.1 Классы вычетов
- 5.2 Системы вычетов
- 5.3 Сравнения в кольце многочленов над полем
6 Решение сравнений
- 6.1 Сравнения первой степени
  - 6.1.1 Примеры
- 6.2 Сравнения второй степени
- 6.3 Системы сравнений
7 Применение
8 См. также
9 Примечания
10 Литература

История

Предпосылкой к созданию теории сравнений стало восстановление сочинений Диофанта, которые были выпущены в подлиннике и с латинским переводом, благодаря Баше де Мезириаку, в 1621 году. Их изучение привело Ферма́ к открытиям, которые по значению существенно опередили своё время. Например, в письме к Френиклю де Бесси^ru_fr^[4] 18 октября 1640 года он сообщил без доказательства теорему, впоследствии получившую название малой теоремы Ферма. В современной формулировке теорема утверждает, что если — простое число и — целое число, не делящееся на , то

$a^{p-1}equiv 1{pmod {p}}$

Первое доказательство этой теоремы принадлежит Лейбницу, причём он открыл указанную теорему независимо от Ферма́ не позднее 1683 года и сообщил об этом с приведением точного доказательства Бернулли. Кроме этого, Лейбницем был предложен прообраз формулировки теоремы Вильсона.

Позже изучение вопросов, посвященных теории чисел и теории сравнений, было продолжено Эйлером, который ввел квадратичный закон взаимности и обобщил теорему Ферма, установив, что

$a^{varphi (n)}equiv 1{pmod {n}},$

где — функция Эйлера.

Понятие и символьное обозначение сравнений было введено Гауссом, как важный инструмент для обоснования его арифметической теории, работа над которой была начата им в 1797 году. В начале этого периода Гауссу ещё не были известны труды его предшественников, поэтому результаты его работы, изложенные в первых трёх главах его книги «Арифметические исследования» (1801 год), были в основном уже известны, однако методы, которые он использовал для доказательств, оказались абсолютно новыми, имеющими высшую важность для развития теории чисел. Используя эти методы Гаусс преобразовал все накопленные до него сведения, связанные с операциями сравнения по модулю, в стройную теорию, которая впервые была изложена в этой же книге. Кроме этого, он исследовал сравнения первой и второй степени, теорию квадратичных вычетов и связанный с ней квадратичный закон взаимности^[5].

Определения

Сравнимость чисел и записывается в виде формулы (сравнения):

Число называется модулем сравнения.

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

Например, числа 32 и -10 сравнимы по модулю 7, так как оба числа при делении на 7 дают остаток 4:

Также числа 32 и -10 сравнимы по модулю 7, так как их разность делится на 7 и к тому же имеет место представление

Свойства сравнимости по модулю

Для фиксированного натурального числа отношение сравнимости по модулю обладает следующими свойствами:

Таким образом, отношение сравнимости по модулю является отношением эквивалентности на множестве целых чисел^[8].

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

Доказательство

Пусть

Следовательно

где

— некое целое число.

Так как является делителем числа , то

где

— некое целое число.

Следовательно

где

по определению.

Следствие:

Для того, чтобы числа

были сравнимы по модулю

, каноническое разложение на простые сомножители которого имеет вид

$m = prod_{i=1}^d p_i^{alpha_i},$

необходимо и достаточно, чтобы

${displaystyle aequiv b{pmod {p_{i}^{alpha _{i}}}},}$

где

^[9].

Операции со сравнениями

Сравнения по одному и тому же модулю обладают многими свойствами обычных равенств. Например, их можно складывать, вычитать и перемножать: если числа $a_{1},a_{2},ldots ,a_{n}$ и $b_{1},b_{2},ldots ,b_{n}$ попарно сравнимы по модулю , то их суммы $a_{1}+a_{2}+ldots +a_{n}$ и ${displaystyle b_{1}+b_{2}+ldots +b_{n}}$ , а также произведения и тоже сравнимы по модулю :

${displaystyle (a_{1}+a_{2}+ldots +a_{n})equiv (b_{1}+b_{2}+ldots +b_{n}){pmod {m}};}$

${displaystyle (a_{1}cdot a_{2}cdot ldots cdot a_{n})equiv (b_{1}cdot b_{2}cdot ldots cdot b_{n}){pmod {m}}.}$

При этом нельзя выполнять эти операции со сравнениями, если их модули не совпадают^[9].

К обеим частям сравнения можно прибавить одно и то же число :

{displaystyle (a+c)equiv (b+c){pmod {m}}.}

Также можно перенести число из одной части сравнения в другую со сменой знака:

Если числа и сравнимы по модулю , то их степени a^k и $b^{k}$ тоже сравнимы по модулю при любом натуральном ^[7]:

${displaystyle a^{k}equiv b^{k}{pmod {m}}.}$

K любой из частей сравнения можно прибавить целое число, кратное модулю, то есть, если числа и сравнимы по модулю некоторого числа , то и a + t_1 сравнимо с ${displaystyle b+t_{2}}$ по модулю , где $t_{1}$ и $t_{2}$ — произвольные целые числа, кратные :

${displaystyle (a+t_{1})equiv (b+t_{2}){pmod {m}}.}$

Также обе части сравнения и модуль можно умножить на одно и то же число, то есть, если числа и сравнимы по модулю некоторого целого числа , то и числа и сравнимы по модулю числа , где — целое:

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

Можно делить обе части сравнения на число, но только взаимно простое с модулем: если

и НОД

то

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

Можно одновременно разделить обе части сравнения и модуль на их общий делитель:

если , то ^[9].

Пример

Применение сравнений позволяет легко получать разнообразные признаки делимости. Например, выведем признак делимости натурального числа N на 7. Запишем в виде (то есть отделим цифру единиц). Условие, что делится нацело на 7, можно записать в виде: Умножим это сравнение на

{displaystyle -20a-2bequiv 0{pmod {7}}.}

Или, прибавив слева число кратное модулю:

Отсюда вытекает следующий признак делимости на 7: надо вычесть из числа десятков удвоенное число единиц, затем повторять эту операцию до тех пор, пока не получится двузначное или однозначное число; если оно делится на 7, то и исходное число делится. Например, пусть Алгоритм проверки^[10]:

${displaystyle N_{1}=2262-2cdot 4=2254; N_{2}=225-2cdot 4=217;N_{3}=21-2cdot 7=7}$

Вывод: 22624 делится на 7.

Связанные определения

Классы вычетов

Множество всех чисел, сравнимых с по модулю , называется классом вычетов по модулю , и обычно обозначается [a]_m или bar a_m . Таким образом, сравнение равносильно равенству классов вычетов ^[11].

Любое число класса называется вычетом по модулю . Пусть для определённости ― остаток от деления любого из представителей выбранного класса на , тогда любое число из этого класса можно представить в виде , где — целое. Вычет, равный остатку ( при ) называется наименьшим неотрицательным вычетом, а вычет rho (), самый малый по абсолютной величине, называется абсолютно наименьшим вычетом. При ${displaystyle r<{frac {m}{2}}}$ получаем, что rho =r , в противном случае . Если — чётное и $r = frac{m}{2}$ , то $rho = -frac{m}{2}$ ^[12].

Поскольку сравнимость по модулю является отношением эквивалентности на множестве целых чисел , то классы вычетов по модулю представляют собой классы эквивалентности; их количество равно .

Множество всех классов вычетов по модулю обозначается $mathbb {Z} _{m}$ или ^[13] или ^[14].

Операции сложения и умножения на индуцируют соответствующие операции на множестве $mathbb {Z} _{m}$ :

${displaystyle [a]_{m}+[b]_{m}=[a+b]_{m};}$

${displaystyle [a]_{m}cdot [b]_{m}=[acdot b]_{m}.}$

Относительно этих операций множество $mathbb {Z} _{m}$ является конечным кольцом, а для простого — конечным полем^[6].

Системы вычетов

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

наименьшие неотрицательные вычеты, то есть числа:

или абсолютно наименьшие вычеты, состоящие из чисел

${displaystyle 0,pm 1,pm 2,ldots ,pm {frac {m-1}{2}}}$

в случае нечётного

, и чисел

${displaystyle 0,pm 1,pm 2,ldots ,pm left({frac {m}{2}}-1right),-{frac {m}{2}}}$

в случае чётного

Максимальный набор попарно несравнимых по модулю чисел, взаимно простых с , называется приведённой системой вычетов по модулю . Всякая приведённая система вычетов по модулю содержит элементов, где — функция Эйлера^[12].

Например, для числа m=42 полная система вычетов может быть представлена числами 0, 1, 2, 3, …, 21, 22, 23, …, 39, 40, 41, а приведённая — 1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41.

Сравнения в кольце многочленов над полем

Рассматривается кольцо многочленов K[x] над полем . Два многочлена $g_{1}$ и
$g_{2}$ , принадлежащие выбранному кольцу, называются сравнимыми по модулю многочлена , если их разность g_1-g_2 делится на без остатка. Сравнение обозначается следующим образом:

${displaystyle g_{1}equiv g_{2}{pmod {f}}.}$

Так же, как и в кольце целых чисел, такие сравнения можно складывать, вычитать и перемножать^[15].

Решение сравнений

Сравнения первой степени

В теории чисел, криптографии и других областях науки часто возникает задача поиска решений сравнения первой степени вида

{displaystyle acdot xequiv b{pmod {m}}.}

Решение такого сравнения начинается с вычисления d = НОД (a,m) . При этом возможны два случая:

${displaystyle a_{1}xequiv b_{1}{pmod {m_{1}}},}$

где ${displaystyle a_{1}={frac {a}{d}},}$

$b_1 = frac{b}{d}$

и $m_1 = frac{m}{d}$

являются целыми числами, причём $a_{1}$

взаимно просты. Поэтому число $a_{1}$

можно обратить по модулю m_1

, то есть найти такое число

, что ${displaystyle ccdot a_{1}equiv 1{pmod {m_{1}}}}$

(другими словами, ${displaystyle cequiv a_{1}^{-1}{pmod {m_{1}}}}$

). Теперь решение находится умножением полученного сравнения на

${displaystyle xequiv ca_{1}xequiv cb_{1}equiv a_{1}^{-1}b_{1}{pmod {m_{1}}}.}$

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

${displaystyle cequiv a_{1}^{-1}equiv a_{1}^{varphi (m_{1})-1}{pmod {m_{1}}}}$

^[16].

Примеры

Пример 1. Для сравнения

имеем d=2 , поэтому по модулю 22 сравнение имеет два решения. Заменим 26 на 4, сравнимое с ним по модулю 22, и затем сократим все три числа на 2:

Поскольку 3 взаимно просто с модулем 11, то его можно обратить по модулю 11 и найти

${displaystyle 3^{-1}equiv 4{pmod {11}}}$

Умножая сравнение на 4, получаем решение по модулю 11:

эквивалентное совокупности двух решений по модулю 22:

Пример 2. Дано сравнение:

Отметим, что модуль 65537

— простое число.

Первый способ решения — воспользоваться соотношением Безу. С помощью алгоритма Евклида или программы, приведенной в статье о соотношении Безу, находим, что это соотношение для чисел 100 и 65537 имеет вид:

{displaystyle 17695cdot 100+(-27)cdot 65537=1,}

или

Умножив обе части этого сравнения на 41, получим:

Отсюда следует, что 725495 есть решение исходного сравнения. Удобнее заменить его на сравнимое с ним 4588 (остаток от деления 725495 на 65537 ). Ответ:

Второй способ решения, более простой и быстрый, не требует построения соотношения Безу, но также эквивалентен алгоритму Евклида.

Шаг 1. Делим модуль на коэффициент при x с остатком: . Умножим обе части исходного сравнения на частное 655 и прибавим 37x ; получим: , но левая часть кратна 65537 , то есть сравнима с нулём, откуда:

{displaystyle 37xequiv -26855{pmod {65537}}}

Мы получили при коэффициент 37 вместо 100. На каждом следующем шаге уменьшаем аналогично, пока не получим единицу.

Шаг 2. Аналогично делим на новый коэффициент при x: . Умножим обе части сравнения, полученного в предыдущем шаге, на частное 1771 и прибавим 10x ; снова заменив левую часть на ноль, получим:

заменяем на его остаток при делении на 65537, равный 45880 :

Далее можно было бы сделать аналогично ещё 5 шагов, но проще разделить обе части сравнения на 10 и сразу получить результат:

Сравнения второй степени

Сравнения второй степени по простому модулю m имеет следующий общий вид:

$c_0x^2+c_1x+c equiv 0pmod {m}.$

Это выражение можно привести к виду:

$(x+b)^2equiv apmod {m}.$

а при замене упрощается максимально:

$(z)^2equiv apmod {m}.$

Решение этого сравнения сводится к выяснению, является ли данное число квадратичным вычетом (с помощью квадратичного закона взаимности) и последующему вычислению квадратного корня по данному модулю^[17]. Для вычисления квадратного корня из квадратичного вычета существует вероятностный метод Берлекэмпа.

Системы сравнений

Китайская теорема об остатках утверждает, что система сравнений с попарно взаимно простыми модулями $m_{1},m_{2},ldots ,m_{n}$ :

${begin{cases}xequiv a_{1}{pmod {m_{1}}}\xequiv a_{2}{pmod {m_{2}}}\ldots \xequiv a_{n}{pmod {m_{n}}}end{cases}}$

всегда разрешима, и её решение единственно по модулю $m_{1}cdot m_{2}cdots m_{n}$ .

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

Применение

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

Например, сравнения часто применяются для вычисления контрольных сумм, используемых в идентификаторах. Так, для определения ошибок при вводе международного номера банковского счета используется сравнение по модулю 97^[18].

В криптографии сравнения можно встретить в системах с открытым ключом, использующих, например, алгоритм RSA или протокол Диффи — Хеллмана. Также, модульная арифметика обеспечивает конечные поля, над которыми затем строятся эллиптические кривые, и используется в различных протоколах с симметричным ключом (AES, IDEA)^[19].

В химии последняя цифра в регистрационном номере CAS является значением контрольной суммы, которая вычисляется путём сложения последней цифры номера, умноженной на 1, второй справа цифры, умноженной на 2, третьей, умноженной на три и так далее до первой слева цифры, завершаясь вычислением остатка от деления на 10^[20]

См. также

Сложение по модулю 2
Возведение в степень по модулю
Показатель числа по модулю
Алгоритмы быстрого возведения в степень по модулю

Примечания

↑ Вельшенбах М. Глава 5. Модульная математика: вычисление в классах вычетов. // Криптография на Си и С++ в действии.. — М.: «Триумф», 2004. — С. 81—95. — 464 с. — ISBN 5-89392-083-X.
↑ Материалы международной научной конференции “Модулярная арифметика”. Виртуальный компьютерный музей (2005). Проверено 31 июля 2010.
↑ Егоров А. А. Сравнения по модулю и арифметика остатков // Квант. — 1970. — № 5. — С. 28—33.
↑ Французский математик, член французской академии наук с 1666.
↑ Вилейтнер Г. Глава III. Теория чисел // История математики от Декарта до середины XIX / пер. с нем. под. ред. А. П. Юшкевича. — М.: Государственное издательство физико-математической литературы, 1960. — С. 69—84. — 467 с.
↑ ¹ ² Степанов С. А. Глава 1. Основные понятия // Сравнения. — М.: «Знание», 1975. — С. 3—9. — 64 с.
↑ ¹ ² Виноградов И. М. Основы теории чисел. — М.-Л.: Гос. изд. технико-теоретической литературы, 1952. — С. 41—45. — 180 с.
↑ Сизый, 2008, с. 88.
↑ ¹ ² ³ Сагалович, 2010, с. 25—29.
↑ Нестеренко, 2008, с. 86—87.
↑ Бухштаб А. А. Глава 8. Классы // Теория чисел. — М.: «Просвещение», 1966. — С. 77—78. — 384 с.
↑ ¹ ² Сагалович, 2010, с. 29—32.
↑ Сизый, 2008, с. 87—88,91.
↑ Лидл Р., Нидеррайтер Г. Конечные поля. В 2-х тт. — М.: Мир, 1998. — С. 27 (Пример 1.37). — 430 с. — ISBN 5-03-000065-8.
↑ Фадеев Д. К. Глава VII. Сравнение в кольце полиномов и расширения полей // Лекции по алгебре. — М.: «Наука», 1984. — С. 197—198. — 416 с.
↑ Сизый, 2008, с. 105—109.
↑ Бухштаб А. А. Глава 21. Сравнения 2-й степени по простому модулю, Глава 22. Сравнения второй степени по составному модулю // Теория чисел. — М.: «Просвещение», 1966. — С. 172—201. — 384 с.
↑ Harald Niederreiter, Arne Winterhof. Applied Number Theory. — «Springer», 2015. — С. 369. — 442 с. — ISBN 978-3-319-22321-6.
↑ Коблиц Н. Курс теории чисел и криптографии / пер. с англ. М. А. Михайловой и В. Е. Тараканова под ред. А. М. Зубкова. — М.: Научное изд-во ТВП, 2001. — С. 96, 105—109, 200—209. — 262 с. — ISBN 5-85484-012-X.
↑ Check Digit Verification of CAS Registry Numbers (англ.).

Литература

Бухштаб А. А. Теория чисел. — М.: «Просвещение», 1966. — 384 с.
Вейль А. Основы теории чисел. — М.: Мир, 1972.
Виленкин Н. Я. Сравнения и классы вычетов // Квант. — 1978. — № 10. — С. 4—8.
Виноградов И. М. Основы теории чисел. — М.-Л.: Гос. изд. технико-теоретической литературы, 1952. — 180 с.
Коблиц Н. Курс теории чисел и криптографии / пер. с англ. М. А. Михайловой и В. Е. Тараканова,под ред. А. М. Зубкова. — М.: Научное изд-во ТВП, 2001. — 254 с. — ISBN 5-85484-012-X.
Материалы международной научной конференции “Модулярная арифметика”. Виртуальный компьютерный музей (2005). Проверено 31 июля 2010.
Нестеренко Ю. В. Теория чисел. — М.: Издательский центр «Академия», 2008. — С. 132—133. — 272 с. — ISBN 9785769546464.
Сагалович Ю. Л. Введение в алгебраические коды — 2-е изд. — М.: ИППИ РАН, 2010. — 320 с. — ISBN 978-5-901158-14-2
Сизый С. В. §4. Теория сравнений // Лекции по теории чисел. — М.: Физматлит, 2008. — 192 с. — ISBN 978-5-9221-0741-9.

Источник

Сравнение чисел по модулю

Определение 1. Если два числа¹) a и b при делении на p дают один и тот же остаток r, то такие числа называются равноостаточными или сравнимыми по модулю p.

Утверждение 1. Пусть p какое нибудь положительное число. Тогда всякое число a всегда и притом единственным способом может быть представлено в виде

где s — число, и r одно из чисел 0,1, …, p−1.

¹) В данной статье под словом число будем понимать целое число.

Действительно. Если s получит значение от −∞ до +∞, то числа sp представляют собой совокупность всех чисел, кратных p. Рассмотрим числа между sp и (s+1)p=sp+p. Так как p целое положительное число, то между sp и sp+p находятся числа

Но эти числа можно получить задав r равным 0, 1, 2,…, p−1. Следовательно sp+r=a получит всевозможные целые значения.

Покажем, что это представление единственно. Предположим, что p можно представить двумя способами a=sp+r и a=s₁p+r₁. Тогда

или

(2)

Так как r₁ принимает один из чисел 0,1, …, p−1, то абсолютное значение r₁−r меньше p. Но из (2) следует, что r₁−r кратно p. Следовательно r₁=r и s₁=s.

Число r называется вычетом числа a по модулю p (другими словами, число r называется остатком от деления числа a на p).

Утверждение 2. Если два числа a и b сравнимы по модулю p, то a−b делится на p.

Действительно. Если два числа a и b сравнимы по модулю p, то они при делении на p имеют один и тот же остаток p. Тогда

где s и s₁ некоторые целые числа.

Разность этих чисел

(3)

делится на p, т.к. правая часть уравнения (3) делится на p.

Утверждение 3. Если разность двух чисел делится на p, то эти числа сравнимы по модулю p.

Доказательство. Обозначим через r и r₁ остатки от деления a и b на p. Тогда

откуда

По утверждению a−b делится на p. Следовательно r−r₁ тоже делится на p. Но т.к. r и r₁ числа 0,1,…, p−1, то абсолютное значение |r−r₁|<p. Тогда, для того, чтобы r−r₁ делился на p должно выполнятся условие r=r₁.

Из утверждения следует, что сравнимые числа — это такие числа, разность которых делится на модуль.

Если нужно записать, что числа a и b сравнимы между собой по модулю p, то пользуются обозначением (введенным Гауссом):

Примеры 25≡39 (mod 7), −18≡14 (mod 4).

Из первого примера следует, что 25 при делении на 7 дает тот же остаток, что и 39. Действительно 25=3·7+4 (остаток 4). 39=3·7+4 (остаток 4). При рассмотрении второго примера нужно учитывать, что остаток должен быть неотрицательным числом, меньшим, чем модуль (т.е. 4). Тогда можно записать: −18=−5·4+2 (остаток 2), 14=3·4+2 (остаток 2). Следовательно −18 при делении на 4 дает остаток 2, и 14 при делении на 4 дает остаток 2.

Свойства сравнений по модулю

Свойство 1. Для любого a и p всегда

Свойство 2. Если два числа a и c сравнимы с числом b по модулю p , то a и c сравнимы между собой по тому же модулю, т.е. если

a≡b mod (p), b≡c mod (p).

то

Действительно. Из условия свойства 2 следует a−b и b−c делятся на p. Тогда их сумма a−b+(b−c)=a−c также делится на p.

Свойство 3. Если

a≡b mod (p) и m≡n mod (p),

то

a+m≡b+n mod (p) и a−m≡b−n mod (p).

Действительно. Так как a−b и m−n делятся на p, то

(a−b)+ (m−n)=(a+m)−(b+n) ,

также делятся на p.

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

Свойство 4. Если

a≡b mod (p) и m≡n mod (p),

то

Действительно.Так как a−b делится на p, то (a−b)m также делится на p, следовательно

Далее m−n делится на p, следовательно b(m−n)=bm−bn также делится на p, значит

Таким образом два числа am и bn сравнимы по модулю с одним и тем же числом bm, следовательно они сравнимы между собой (свойство 2).

Свойство 5. Если

то

где k некоторое неотрицательное целое число.

Действительно. Имеем a≡b mod (p). Из свойства 4 следует

Все свойства 1-5 представить в следующем утверждении:

Утверждение 4. Пусть f(x₁, x₂, x₃, …) целая рациональная функция с целыми коэффициентами и пусть

a₁≡b₁, a₂≡b₂, a₃≡b₃, … mod (p).

тогда

f(a₁, a₂, a₃, …)≡f(b₁, b₂, b₃, …) mod (p).

При делении все обстоит иначе. Из сравнения

не всегда следует сравнение

Утверждение 5. Пусть

тогда

где λ это наибольший общий делитель чисел m и p.

Доказательство. Пусть λ наибольший общий делитель чисел m и p. Тогда

Так как m(a−b) делится на k, то

имеет нулевой остаток. Тогда

Следовательно

имеет нулевой остаток, т.е. m₁(a−b) делится на k₁. Но числа m₁ и k₁ числа взаимно простые. Следовательно a−b делится на k₁=k/λ и, тогда, a≡b mod (p/λ).

Утверждение 6. Если

и m является один из делителей числа p, то

Действительно. a−b делится на p. p делится на m. Следовательно a−b делится на m.

Утверждение 7. Если

a≡b mod (p), a≡b mod (q), a≡b mod (s)

то

где h наименьшее общее кратное чисел p,q,s.

Действительно. Разность a≡b должна быть числом, кратным p,q,s. и, следовательно должна быть кратным h.

В частном случае, если модули p,q,s взаимно простые числа, то

где h=pqs.

Заметим, что можно допустить сравнения по отрицательным модулям, т.е. сравнение a≡b mod (p) означает и в этом случае, что разность a−b делится на p. Все свойства сравнений остаются в силе и для отрицательных модулей.

Источник

Содержание

1 Сравнения по модулю
2 Арифметика сравнений
- 2.1 Свойства сравнений
3 Полная и приведенная система вычетов
4 Решение линейных систем по модулю
- 4.1 Примеры решения

Сравнения по модулю

Будем рассматривать целые числа в связи с остатками от деления их на данное целое число m, которое назовем модулем.
Каждому целому числу отвечает определенный остаток от деления его на m. Если двум целым a и b отвечает один и тот же остаток r, то они называются сравнимыми по модулю m.

Сравнимость для a и b записывается так :

Сравнимость чисел a и b по модулю m равносильна:

а. Возможности представить a в форме , где t — целое.
б. Делимости на m.
- Действительно, из следует , откуда , и , где .
- Обратно, из , представляя b в форме , выводим , где , значит .

Арифметика сравнений

Свойства сравнений

1. Два числа, сравнимые с третьим сравнимы между собой.
- Легко выводится из пункта «а».

2. Сравнения можно почленно складывать.
- Представляем сравнения, как в пункте «а» и складываем.

3. Сравнения можно почленно перемножать.
- Представляем сравнения, как в пункте «а», перемножаем, получим , где N—целое.

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

5. Обе части сравнения можно умножить на одно и тоже число.
- Действительно, из , следует , и, следовательно, .

6. Обе части сравнения и модуль можно разделить на их общий делитель.
- Действительно, пусть , отсюда , и, следовательно, .

7. Если сравнение имеет место по нескольким модулям, то оно имеет место и по модулю равному НОК этих модулей.
- В самом деле, из следует, что разность делится на все модули . Поэтому она должна делиться и на их НОК.

8. Если сравнение имеет место по модулю m, то оно имеет место и по модулю d, равному любому делителю числа m.
- Следует из пункта «б».

9. Если одна часть сравнения и модуль делятся на некоторое число, то и другая сторона сравнения должна делиться на это число.
- Следует из пункта «а».

10. Если , то .
- Следует из пункта «а» по свойству НОДа.

Полная и приведенная система вычетов

Числа равноостаточные(сравнимые по модулю m) образуют класс чисел по модулю m.
Из такого определения следует, что всем числам класса отвечает один остаток r, и мы получим все числа класса,
если в форме заставим t пробегать все целые числа. Таким образом для каждого значения остатка имеется свой класс чисел.

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

Любые m чисел, попарно несравнимые по модулю m, образуют полную систему вычетов по этому модулю.

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

Решение линейных систем по модулю

Пусть . Сравнение невозможно, если b не делится на d. При b, кратном d, сравнение имеет d решений.
Поиск решений:
,
Составим новое сравнение ,
обозначим его . Пусть его решением будет , тогда остальные решения найдутся по следующей формуле: (следует понимать, что вычет по модулю, поэтому в этой формуле можно сменить знак, для удобства), всего решений будет d. Если нахождение не является очевидным, то следует воспользоваться теорией цепных дробей, и тогда , где — числитель подходящей дроби.

Примеры решения

Пример 1.

Найдем НОД
Перейдем к новому сравнению
Легко находится
Тогда ответом будет

Пример 2.

Найдем НОД , 75 кратно 3, значит имеем 3 решения
Перейдем к новому сравнению
Воспользуемся цепными дробями, в нашем случае , значит
Тогда ответом будет .

Источник