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

Если два целых числа 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}}} . Правила сокращения для сравнений следующие.

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

a d ≡ b d (mod m) {\displaystyle {ad}\equiv {bd}{\pmod {m}}} и НОД (d , m) = 1 , {\displaystyle {(d,m)=1},} то .

Если, число 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} берётся одно из двух множеств:

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

0 , 1 , … , m − 1 {\displaystyle 0,1,\ldots ,m-1}

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

0 , ± 1 , ± 2 , … , ± m − 1 2 {\displaystyle 0,\pm 1,\pm 2,\ldots ,\pm {\frac {m-1}{2}}} , в случае нечётного m {\displaystyle m} , и чисел 0 , ± 1 , ± 2 , … , ± (m 2 − 1) , m 2 {\displaystyle 0,\pm 1,\pm 2,\ldots ,\pm ({\frac {m}{2}}-1),{\frac {m}{2}}} в случае чётного 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} ; снова заменив левую часть на ноль, получим.

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

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

Число а , сравнимо с 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 и 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 случая:

• Если b не кратно d , то у сравнения нет решений.
• Если b кратно d , то у сравнения существует единственное решение по модулю m / d , или, что то же самое, d решений по модулю m . В этом случае в результате сокращения исходного сравнения на d получается сравнение:

где 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 год . Он же предложил утвердившуюся в математике символику для сравнений.