Числа подобные по модулю. Сравнение по модулю

Сравнение с одним неизвестным x имеет вид

Где . Еслиa n не делится на m , то и называется степенью сравнения.

Решением сравнения называется всякое целое число x 0 , для которого

Если х 0 удовлетворяет сравнению, то, согласно свойству 9 сравнений, этому сравнению будут удовлетворять все целые числа, сравнимые с x 0 по модулю m . Поэтому все решения сравнения, принадлежащие одному классу вычетов по модулю т , будем рассматривать как одно решение. Таким образом, сравнение имеет столько решений, сколько элементов полной системы вычетов ему удовлетворяет.

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

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

Сравнение первой степени с одним неизвестным х имеет вид

(2.2)

Теорема2.4. Для того чтобы сравнение имело хотя бы одно решение, необходимо и достаточно, чтобы число b делилось на НОД(a , m ).

Доказательство. Сначала докажем необходимость. Пусть d = НОД(a , m ) и х 0 - решение сравнения. Тогда, то есть разностьах 0 − b делится на т. Значит, существует такое целое число q , что ах 0 − b = qm . Отсюда b = ах 0 − qm . А поскольку d , как общий делитель, делит числа а и т, то уменьшаемое и вычитаемое делятся на d , а значит и b делится на d .

Теперь докажем достаточность. Пусть d - наибольший общий делитель чисел а и т, и b делится на d . Тогда по определению делимости существуют такие целые числа a 1 , b 1 ,т 1 , что.

Расширенным алгоритмом Евклида найдем линейное представление числа 1 = НОД(a 1 , m 1 ):

для некоторых x 0 , y 0 . Домножим обе части последнего равенства на b 1 d :

или, что то же самое,

,

то есть , и- решение сравнения. □

Пример2.10. Сравнение 9х = 6 (mod 12) имеет решение, так как НОД(9, 12) = 3 и 6 делится на 3. □

Пример2.11. Сравнение 6х = 9 (mod 12) не имеет решений, так как НОД(6, 12) = 6, а 9 не делится на 6. □

Теорема 2.5. Пусть сравнение (2.2) разрешимо и d = НОД(a , m ). Тогда множество решений сравнения (2.2) состоит из d классов вычетов по модулю т, а именно, если х 0 - одно из решений, то все другие решения - это

Доказательство. Пусть х 0 - решение сравнения (2.2), то есть и, . Значит, существует такое q , что ах 0 − b = qm . Подставляя теперь в последнее равенство вместо х 0 произвольное решение вида, где, получаем выражение

, делящееся на m . □

Пример 2.12. Сравнение 9х =6 (mod 12) имеет ровно три решения, так как НОД(9, 12)=3. Эти решения: х 0 = 2, х 0 + 4 = 6, х 0 + 2∙4=10.□

Пример2.13. Сравнение 11х =2 (mod 15) имеет единственное решение х 0 = 7,таккакНОД(11,15)=1.□

Покажем, как решать сравнение первой степени. Не умаляя общности, будем считать, что НОД(a , т) = 1. Тогда решение сравнения (2.2) можно искать, например, по алгоритму Евклида. Действительно, используя расширенный алгоритм Евклида, представим число 1 в виде линейной комбинации чисел a и т :

Умножим обе части этого равенства на b , получим: b = abq + mrb , откуда abq - b = - mrb , то есть a ∙ (bq ) = b (mod m ) и bq - решение срав­нения (2.2).

Еще один путь решения - использовать теорему Эйлера. Опять считаем, что НОД(а, т) = 1. Применяем теорему Эйлера: . Умножим обе части сравнения наb : . Переписывая последнее выражение в виде , получаем, что- решение сравнения (2.2).

Пусть теперь НОД(a , m ) = d >1. Тогда a = a t d , m = m t d , где НОД(а 1 , m 1) = 1. Кроме того, необходимо b = b 1 d , для того чтобы сравнение было разрешимо. Если х 0 - решение сравнения а 1 x = b 1 (mod m 1), причем единственное, поскольку НОД(а 1 , m 1) = 1, то х 0 будет решением и сравнения а 1 xd = db 1 (mod m 1), то есть исходного сравнения (2.2). Остальные d - 1 решений находим по теореме 2.5.

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

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

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

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

(2)

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

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

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

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

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

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

Доказательство. Обозначим через r и r 1 остатки от деления 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 всегда

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

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

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

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

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

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

где h=pqs.

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

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

Обобщая этот случай, будем говорить, что два целых числа, отличающиеся на кратное какого-нибудь фиксированного натурального числа, эквивалентны. На этом основано понятие сравнимости по модулю, введенное Гауссом.

Число а , сравнимо с b по модулю m , если их разность делится на фиксированное натуральное число m , то есть а - b делится на m . Символически это записывается в виде:

а ≡ b(mod m) ,

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

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

Например, числа 7 и 19 сравнимы по модулю 4, но не сравнимы по модулю 5, т.к. 19-7=12 делится на 4 и не делится на 5.

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

x=km+r, r = 0, 1, 2, ... , m-1 .

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

Примеры использования сравнений доставляются хорошо известными признаками делимости. Обычное представление числа n цифрами в десятичной системе счисления имеет вид:

n = c10 2 + b10 1 + a10 0 ,

где а, b, с, - цифры числа, записанные справа налево, так что а - число единиц, b - числе десятков и т.д. Так как 10 k ≡ 1(mod9) при любом к≥0, то из написанного следует, что

n ≡ c + b + a (mod9),

откуда вытекает признак делимости на 9: n делится на 9 тогда и только тогда, когда сумма его цифр делится на 9. Это рассуждение проходит также и при замене 9 на 3.

Получим признак делимости на 11. Имеют место сравнения:

10≡- 1(mod11), 10 2 ≡ 1(mod11) 10 3 ≡- 1(mod11), и так далее. Поэтому n ≡ c - b + a - …. (mod11).

Следовательно, n делится на 11 тогда и только тогда, когда знакопеременная сумма его цифр а - b + с -... делится на 11.

Например, знакопеременная сумма цифр числа 9581 есть 1 - 8 + 5 - 9 = -11, она делится на 11, значит и число 9581 делится на 11.

Если имеют места сравнения: , то их можно почленно складывать, вычитать и перемножать так же, как и равенства:

Сравнение всегда можно умножить на целое число:

если , то

Однако сокращение сравнения на какой-либо множитель не всегда возможно, Например, , но нельзя произвести сокращение на общий для чисел 42 и 12 множитель 6; такое сокращение приводит к неверному результату, поскольку .

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

Выше было уже отмечено, что любое целое число сравнимо по mod m с одним из следующих чисел: 0, 1, 2,... , m-1.

Помимо этого ряда, имеются и другие ряды чисел, обладающие тем же свойством; так, например, любое число сравнимо по mod 5 с одним из следующих чисел: 0, 1, 2, 3, 4, но так же сравнимо с одним из следующих чисел: 0, -4, -3, -2, -1, или 0, 1, -1, 2, -2. Любой такой ряд чисел называется полной системой вычетов по модулю 5.

Таким образом, полной системой вычетов по modm называется любой ряд из m чисел, никакие два из которых несравнимы друг с другом. Обычно используется полная система вычетов, состоящая из чисел: 0, 1, 2, ..., m -1. Вычетом числа n по модулю m является остаток от деления n на m , что следует из представления n = km + r , 0<r <m - 1.

Если два целых числа a {\displaystyle a} и b {\displaystyle b} при делении на m {\displaystyle m} дают одинаковые остатки, то они называются сравнимыми (или равноостаточными ) по модулю числа m {\displaystyle m} . Шаблон:/рамка Сравнимость чисел a {\displaystyle a} и b {\displaystyle b} записывается в виде формулы (сравнения ):

Число m {\displaystyle m} называется модулем сравнения.

Определение сравнимости чисел a {\displaystyle a} и b {\displaystyle b} по модулю m {\displaystyle m} равносильно любому из следующих утверждений:

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

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

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

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

Так как d {\displaystyle d} является делителем числа m {\displaystyle m} , то

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

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

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

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

Так как разность a − b {\displaystyle a-b} кратна каждому , то она кратна и их наименьшему общему кратному

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

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

Сравнения по одному и тому же модулю обладают многими свойствами обычных равенств. Например, их можно складывать, вычитать и перемножать: если числа a 1 , a 2 , . . . , a n {\displaystyle a_{1},a_{2},...,a_{n}} и b 1 , b 2 , . . . , b n {\displaystyle b_{1},b_{2},...,b_{n}} попарно сравнимы по модулю m {\displaystyle m} , то их суммы a 1 + a 2 + . . . + a n {\displaystyle a_{1}+a_{2}+...+a_{n}} и b 1 + b 2 + . . . + b n {\displaystyle b_{1}+b_{2}+...+b_{n}} , а также произведения a 1 ⋅ a 2 ⋅ . . . ⋅ a n {\displaystyle a_{1}\cdot a_{2}\cdot ...\cdot a_{n}} и b 1 ⋅ b 2 ⋅ . . . ⋅ b n {\displaystyle b_{1}\cdot b_{2}\cdot ...\cdot b_{n}} тоже сравнимы по модулю m {\displaystyle m} . При этом нельзя выполнять эти операции со сравнениями, если их модули не совпадают .

Отдельно, следует отметить, что к обеим частям сравнения можно прибавить одно и то же число, также можно перенести число из одной части сравнения в другую со сменой знака. Если числа a {\displaystyle a} и b {\displaystyle b} сравнимы по модулю m {\displaystyle m} , то их степени a k {\displaystyle a^{k}} и b k {\displaystyle b^{k}} тоже сравнимы по модулю m {\displaystyle m} при любом натуральном k {\displaystyle k} .

K любой из частей сравнения можно прибавить целое число, кратное модуля, то есть, если числа a {\displaystyle a} и b {\displaystyle b} сравнимы по модулю некоторого числа m {\displaystyle m} , то и a + t 1 {\displaystyle a+t_{1}} сравнимо с b + t 2 {\displaystyle b+t_{2}} по модулю m {\displaystyle m} ( t 1 {\displaystyle t_{1}} и t 2 {\displaystyle t_{2}} - произвольные целые числа) .Также обе части сравнения и модуль можно умножить на одно и то же число, то есть, если числа a {\displaystyle a} и b {\displaystyle b} сравнимы по модулю некоторого целого числа m {\displaystyle m} , то и числа a q {\displaystyle aq} и b q {\displaystyle bq} сравнимы по модулю числа m q {\displaystyle mq} ,где q {\displaystyle q} - целое .

Сравнения, однако, нельзя, вообще говоря, делить друг на друга или на другие числа. Пример: 14 ≡ 20 (mod 6) {\displaystyle 14\equiv 20{\pmod {6}}} , однако, сократив на 2, мы получаем ошибочное сравнение: 7 ≡ 10 (mod 6) {\displaystyle 7\equiv 10{\pmod {6}}} . Правила сокращения для сравнений следующие.

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

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

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

если a c ≡ b c (mod m c) {\displaystyle {ac}\equiv {bc}{\pmod {mc}}} , то a ≡ b (mod m) {\displaystyle a\equiv b{\pmod {m}}} .

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

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

Множество всех чисел, сравнимых с a {\displaystyle a} по модулю m {\displaystyle m} , называется классом вычетов a {\displaystyle a} по модулю m {\displaystyle m} , и обычно обозначается [ a ] m {\displaystyle [a]_{m}} или a ¯ m {\displaystyle {\bar {a}}_{m}} . Таким образом, сравнение a ≡ b (mod m) {\displaystyle a\equiv b{\pmod {m}}} равносильно равенству классов вычетов [ a ] m = [ b ] m {\displaystyle [a]_{m}=[b]_{m}} .

Любое число класса называется вычетом по модулю m {\displaystyle m} . Пусть для определенности r {\displaystyle r} ―остаток от деления любого из представителей выбранного класса на m {\displaystyle m} , тогда любое число q {\displaystyle q} из этого класса можно представить в виде q = m t + r {\displaystyle q=mt+r} , где t {\displaystyle t} -целое . Вычет равный остатку r {\displaystyle r} называется наименьшим неотрицательным вычетом , а вычет ρ {\displaystyle \rho } , самый малый по абсолютной величине, называется абсолютно наименьшим вычетом . При r < m 2 {\displaystyle r<{\frac {m}{2}}} получаем, что ρ = r {\displaystyle \rho =r} , в противном случае ρ = r − m {\displaystyle \rho =r-m} . Если m {\displaystyle m} -чётное и r = m 2 {\displaystyle r={\frac {m}{2}}} , то ρ = − m 2 {\displaystyle \rho =-{\frac {m}{2}}} .

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

Множество всех классов вычетов по модулю m {\displaystyle m} обозначается или Z / m Z {\displaystyle \mathbb {Z} /m\mathbb {Z} } или Z / (m) {\displaystyle \mathbb {Z} /(m)} .

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

Относительно этих операций множество Z m {\displaystyle \mathbb {Z} _{m}} является конечным кольцом , а для простого m {\displaystyle m} - конечным полем .

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

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

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

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

Максимальный набор попарно несравнимых по модулю m {\displaystyle m} чисел, взаимно простых с m {\displaystyle m} , называется приведённой системой вычетов по модулю m {\displaystyle m} . Всякая приведённая система вычетов по модулю m {\displaystyle m} содержит φ (m) {\displaystyle \varphi (m)} элементов, где φ (⋅) {\displaystyle \varphi (\cdot)} - функция Эйлера .

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

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

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

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

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

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

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

Примеры

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

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

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

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

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

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

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

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

Отсюда следует, что есть решение исходного сравнения. Удобнее заменить его на сравнимое с ним 4588 {\displaystyle 4588} (остаток от деления 725495 {\displaystyle 725495} на 65537 {\displaystyle 65537} ). Ответ: x ≡ 4588 (mod 65537) . {\displaystyle x\equiv 4588{\pmod {65537}}.}

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

Шаг 1. Делим модуль на коэффициент при x с остатком: 65537 = 100 ⋅ 655 + 37 {\displaystyle 65537=100\cdot 655+37} . Умножим обе части исходного сравнения на частное 655 {\displaystyle 655} и прибавим 37 x {\displaystyle 37x} ; получим: 65537 x ≡ 26855 + 37 x (mod 65537) {\displaystyle 65537x\equiv 26855+37x{\pmod {65537}}} , но левая часть кратна 65537 {\displaystyle 65537} , то есть сравнима с нулём, откуда:

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

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