Два целых числа a и b сравнимы по модулю натурального числа n (или равноостаточны при делении на n), если при делении на n они дают одинаковые остатки.
Эквивалентные формулировки: a и b сравнимы по модулю n , если их разность a - b делится на n , или если a может быть представлено в виде a = b + k n , где k - некоторое целое число. Например: 32 и −10 сравнимы по модулю 7, так как
Утверждение « a и b сравнимы по модулю n » записывается в виде:
Отношение сравнения по модулю обладает свойствами
Любые два целых числа a и b сравнимы по модулю 1.
Для того, чтобы числа a и b были сравнимы по модулю n , необходимо и достаточно, чтобы их разность делилась на n .
Если числа и попарно сравнимы по модулю n , то их суммы и , а также произведения и тоже сравнимы по модулю n .
Если числа a и b сравнимы по модулю n , то их степени a k и b k тоже сравнимы по модулю n при любом натуральном k .
Если числа a и b сравнимы по модулю n , и n делится на m , то a и b сравнимы по модулю m .
Для того, чтобы числа a и b были сравнимы по модулю n , представленному в виде его канонического разложения на простые сомножители p i
необходимо и достаточно, чтобы
Отношение сравнения является отношением эквивалентности и обладает многими свойствами обычных равенств. Например, их можно складывать и перемножать: если
Сравнения, однако, нельзя, вообще говоря, делить друг на друга или на другие числа. Пример: , однако, сократив на 2, мы получаем ошибочное сравнение: . Правила сокращения для сравнений следующие.
Нельзя также выполнять операции со сравнениями, если их модули не совпадают.
Другие свойства:
Множество всех чисел, сравнимых с a по модулю n называется классом вычетов a по модулю n , и обычно обозначается [a ] n или . Таким образом, сравнение равносильно равенству классов вычетов [a ] n = [b ] n .
Поскольку сравнение по модулю n является отношением эквивалентности на множестве целых чисел , то классы вычетов по модулю n представляют собой классы эквивалентности; их количество равно n . Множество всех классов вычетов по модулю n обозначается или .
Операции сложения и умножения на индуцируют соответствующие операции на множестве :
[a ] n + [b ] n = [a + b ] nОтносительно этих операций множество является конечным кольцом , а если n простое - конечным полем .
Система вычетов позволяет осуществлять арифметические операции над конечным набором чисел, не выходя за его пределы. Полная система вычетов по модулю n ― любой набор из n несравнимых между собой по модулю n целых чисел. Обычно в качестве полной системы вычетов по модулю n берутся наименьшие неотрицательные вычеты
0,1,...,n − 1или абсолютно наименьшие вычеты, состоящие из чисел
,в случае нечётного n и чисел
в случае чётного n .
В теории чисел , криптографии и других областях науки часто возникает задача отыскания решений сравнения первой степени вида:
Решение такого сравнения начинается с вычисления НОД (a, m)=d . При этом возможны 2 случая:
где a 1 = a / d , b 1 = b / d и m 1 = m / d являются целыми числами, причем a 1 и m 1 взаимно просты. Поэтому число a 1 можно обратить по модулю m 1 , то есть найти такое число c , что (другими словами, ). Теперь решение находится умножением полученного сравнения на c :
Практическое вычисление значения c можно осуществить разными способами: с помощью теоремы Эйлера , алгоритма Евклида , теории цепных дробей (см. алгоритм) и др. В частности, теорема Эйлера позволяет записать значение c в виде:
Для сравнения имеем d = 2 , поэтому по модулю 22 сравнение имеет два решения. Заменим 26 на 4, сравнимое с ним по модулю 22, и затем сократим все 3 числа на 2:
Поскольку 2 взаимно просто с модулем 11, можно сократить левую и правую части на 2. В итоге получаем одно решение по модулю 11: , эквивалентное двум решениям по модулю 22: .
Решение сравнений второй степени сводится к выяснению, является ли данное число квадратичным вычетом (с помощью квадратичного закона взаимности) и последующему вычислению квадратного корня по данному модулю.
Китайская теорема об остатках , известная уже много столетий, утверждает (на современном математическом языке), что кольцо вычетов по модулю произведения нескольких взаимно простых чисел является прямым произведением соответственных множителям колец вычетов.
В значительной степени теория делимости и вычетов была создана Эйлером . Сравнения по модулю впервые использовались Гауссом в его книге «Арифметические исследования», 1801 год . Он же предложил утвердившуюся в математике символику для сравнений.
ПЕРВУШКИН БОРИС НИКОЛАЕВИЧ
ЧОУ «Санкт-Петербургская Школа «Тет-а-Тет»
Учитель Математики Высшей категории
Сравнение чисел по модулю
Определение 1. Если два числа 1 ) a и b при делении на p дают один и тот же остаток r , то такие числа называются равноостаточными или сравнимыми по модулю p .
Утверждение 1. Пусть p какое нибудь положительное число. Тогда всякое число a всегда и притом единственным способом может быть представлено в виде
| a=sp+r , | (1) |
где s - число, и r одно из чисел 0,1, ..., p −1.
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 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 . Тогда
где s и s 1 некоторые целые числа.
Разность этих чисел
| (3) |
делится на p , т.к. правая часть уравнения (3) делится на p .
Утверждение 3. Если разность двух чисел делится на p , то эти числа сравнимы по модулю p .
Доказательство. Обозначим через r и r 1 остатки от деления a и b на p . Тогда
откуда
По утверждению a−b делится на p . Следовательно r − r 1 тоже делится на p . Но т.к. r и r 1 числа 0,1,..., p −1, то абсолютное значение | r − r 1 |< p . Тогда, для того, чтобы r − r 1 делился на p должно выполнятся условие r = r 1 .
Из утверждения следует, что сравнимые числа - это такие числа, разность которых делится на модуль.
Если нужно записать, что числа a и b сравнимы между собой по модулю p , то пользуются обозначением (введенным Гауссом):
| a≡b mod( 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 всегда
| a≡a mod ( p ). |
Свойство 2. Если два числа a и c сравнимы с числом b по модулю p , то a и c сравнимы между собой по тому же модулю, т.е. если
| a≡b mod ( p ), b≡c mod ( p ). |
то
| a≡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 ) , |
| ( a−b )−( m−n )=( a−m )−( b−n ) |
также делятся на p .
Это свойство можно распространить на какое угодно число сравнений, имеющих один и тот же модуль.
Свойство 4. Если
| a≡b mod ( p ) и m≡n mod ( p ), |
то
Далее m−n делится на p , следовательно b(m−n)=bm−bn также делится на p , значит
| bm≡bn mod ( p ). |
Таким образом два числа am и bn сравнимы по модулю с одним и тем же числом bm , следовательно они сравнимы между собой (свойство 2).
Свойство 5. Если
| a≡b mod ( p ). |
то
| a k ≡b k mod ( p ). |
где k некоторое неотрицательное целое число.
Действительно. Имеем a≡b mod ( p ). Из свойства 4 следует
| ................. |
| a k ≡b k mod ( p ). |
Все свойства 1-5 представить в следующем утверждении:
Утверждение 4. Пусть f ( x 1 , x 2 , x 3 , ...) целая рациональная функция с целыми коэффициентами и пусть
| a 1 ≡ b 1 , a 2 ≡ b 2 , a 3 ≡ b 3 , ... mod ( p ). |
тогда
| f ( a 1 , a 2 , a 3 , ...)≡ f ( b 1 , b 2 , b 3 , ...) mod ( p ). |
При делении все обстоит иначе. Из сравнения
Утверждение 5. Пусть
где λ это наибольший общий делитель чисел m и p .
Доказательство. Пусть λ наибольший общий делитель чисел m и p . Тогда
Так как m(a−b) делится на k , то
имеет нулевой остаток, т.е. m 1 ( a−b ) делится на k 1 . Но числа m 1 и k 1 числа взаимно простые. Следовательно a−b делится на k 1 = k/λ и, тогда, p,q,s.
Действительно. Разность a≡b должна быть числом, кратным p,q,s. и, следовательно должна быть кратным h .
В частном случае, если модули p,q,s взаимно простые числа, то
| a≡b mod ( h ), |
где 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} равносильно любому из следующих утверждений:
Доказательство
Кроме вышеперечисленных свойств, для сравнений справедливы следующие утверждения:
Доказательство
a ≡ b (mod m) . {\displaystyle a\equiv b{\pmod {m}}.}Следовательно,
a − b = m t . {\displaystyle a-b=mt.}Так как d {\displaystyle d} является делителем числа m {\displaystyle m} , то
m = c d {\displaystyle m=cd} .Следовательно,
a − b = m t = c d t = q d , (q = c t) {\displaystyle a-b=mt=cdt=qd,(q=ct)} a ≡ b (mod d) {\displaystyle a\equiv b{\pmod {d}}}по определению.
Доказательство
a ≡ b (mod m i) , i = 1 , 2 , . . . , k . {\displaystyle a\equiv b{\pmod {m_{i}}},i=1,2,...,k.}Следовательно,
a − b = m i t . {\displaystyle a-b=m_{i}t.}Так как разность a − b {\displaystyle a-b} кратна каждому , то она кратна и их наименьшему общему кратному
Следствие: Для того, чтобы числа a {\displaystyle a} и b {\displaystyle b} были сравнимы по модулю m {\displaystyle m} , каноническое разложение на простые сомножители которого имеет вид m = ∏ i = 1 d p i α i , {\displaystyle m=\prod _{i=1}^{d}p_{i}^{\alpha _{i}},}необходимо и достаточно, чтобы
a ≡ b (mod p i α i) , i = 1 , 2 , … , d {\displaystyle a\equiv b{\pmod {p_{i}^{\alpha _{i}}}},\quad i=1,2,\dots ,d} .Сравнения по одному и тому же модулю обладают многими свойствами обычных равенств. Например, их можно складывать, вычитать и перемножать: если числа 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}} :
[ a ] m + [ b ] m = [ a + b ] m {\displaystyle [a]_{m}+[b]_{m}=_{m}} [ a ] m ⋅ [ b ] m = [ a ⋅ b ] m {\displaystyle [a]_{m}\cdot [b]_{m}=_{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} .
В теории чисел , криптографии и других областях науки часто возникает задача поиска решений сравнения первой степени вида:
a x ≡ b (mod m) . {\displaystyle ax\equiv b{\pmod {m}}.}Решение такого сравнения начинается с вычисления d = {\displaystyle d=} НОД (a , m) {\displaystyle (a,m)} . При этом возможны 2 случая:
a 1 x ≡ b 1 (mod m 1) {\displaystyle a_{1}x\equiv b_{1}{\pmod {m_{1}}}} где a 1 = a d {\displaystyle a_{1}={\frac {a}{d}}} , b 1 = b d {\displaystyle b_{1}={\frac {b}{d}}} и m 1 = m d {\displaystyle m_{1}={\frac {m}{d}}} являются целыми числами , причем и m 1 {\displaystyle m_{1}} взаимно просты. Поэтому число a 1 {\displaystyle a_{1}} можно обратить по модулю m 1 {\displaystyle m_{1}} , то есть найти такое число c {\displaystyle c} , что c ⋅ a 1 ≡ 1 (mod m 1) {\displaystyle c\cdot a_{1}\equiv 1{\pmod {m_{1}}}} (другими словами, c ≡ a 1 − 1 (mod m 1) {\displaystyle c\equiv a_{1}^{-1}{\pmod {m_{1}}}} ). Теперь решение находится умножением полученного сравнения на c {\displaystyle c} : x ≡ c a 1 x ≡ c b 1 ≡ a 1 − 1 b 1 (mod m 1) . {\displaystyle x\equiv ca_{1}x\equiv cb_{1}\equiv a_{1}^{-1}b_{1}{\pmod {m_{1}}}.}Практическое вычисление значения c {\displaystyle c} можно осуществить разными способами: с помощью теоремы Эйлера , алгоритма Евклида , теории цепных дробей (см. алгоритм) и др. В частности, теорема Эйлера позволяет записать значение c {\displaystyle c} в виде:
c ≡ a 1 − 1 ≡ a 1 φ (m 1) − 1 (mod m 1) {\displaystyle c\equiv a_{1}^{-1}\equiv a_{1}^{\varphi (m_{1})-1}{\pmod {m_{1}}}} .Пример 1. Для сравнения
6 x ≡ 26 (mod 22) {\displaystyle 6x\equiv 26{\pmod {22}}}имеем d = 2 {\displaystyle d=2} , поэтому по модулю 22 сравнение имеет два решения. Заменим 26 на 4, сравнимое с ним по модулю 22, и затем сократим все три числа на 2:
3 x ≡ 2 (mod 11) {\displaystyle 3x\equiv 2{\pmod {11}}}Поскольку 3 взаимно просто с модулем 11, то его можно обратить по модулю 11 и найти
3 − 1 ≡ 4 (mod 11) {\displaystyle 3^{-1}\equiv 4{\pmod {11}}} .Умножая сравнение на 4, получаем решение по модулю 11:
x ≡ 8 (mod 11) {\displaystyle x\equiv 8{\pmod {11}}} ,эквивалентное совокупности двух решений по модулю 22:
x ≡ 8 (mod 22) {\displaystyle x\equiv 8{\pmod {22}}} и x ≡ 19 (mod 22) {\displaystyle x\equiv 19{\pmod {22}}} .Пример 2. Дано сравнение:
100 x ≡ 41 (mod 65537) . {\displaystyle 100x\equiv 41{\pmod {65537}}.} Отметим, что модуль - простое число.Первый способ решения - воспользоваться соотношением Безу . С помощью алгоритма Евклида или программы, приведенной в статье о соотношении Безу, находим, что это соотношение для чисел 100 {\displaystyle 100} и 65537 {\displaystyle 65537} имеет вид:
17695 ⋅ 100 + (− 27) ⋅ 65537 = 1 , {\displaystyle 17695\cdot 100+(-27)\cdot 65537=1,} или 17695 ⋅ 100 ≡ 1 (mod 65537) {\displaystyle 17695\cdot 100\equiv 1{\pmod {65537}}}Умножив обе части этого сравнения на 41, получим:
100 ⋅ 725495 ≡ 41 (mod 65537) {\displaystyle 100\cdot 725495\equiv 41{\pmod {65537}}}Отсюда следует, что есть решение исходного сравнения. Удобнее заменить его на сравнимое с ним 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} , то есть сравнима с нулём, откуда:
37 x ≡ − 26855 (mod 65537) {\displaystyle 37x\equiv -26855{\pmod {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} ; снова заменив левую часть на ноль, получим.
