Если два целых числа 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} ; снова заменив левую часть на ноль, получим.
Сравнение с одним неизвестным x имеет вид
Где . Еслиa n не делится на m , то и называется степенью сравнения.
Решением сравнения называется всякое целое число x 0 , для которого
Если х 0 удовлетворяет сравнению, то, согласно свойству 9 сравнений, этому сравнению будут удовлетворять все целые числа, сравнимые с x 0 по модулю m . Поэтому все решения сравнения, принадлежащие одному классу вычетов по модулю т , будем рассматривать как одно решение. Таким образом, сравнение имеет столько решений, сколько элементов полной системы вычетов ему удовлетворяет.
Сравнения, множества решений которых совпадают, называются равносильными.
Сравнение первой степени с одним неизвестным х имеет вид
(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 . Все свойства сравнений остаются в силе и для отрицательных модулей.
Два целых числа 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 год . Он же предложил утвердившуюся в математике символику для сравнений.
Для двух целых числа х и у введем отношение сравнимости по четности, если их разность - четное число. Легко проверить, что при этом выполняются все три ранее введенные условия эквивалентности. Введенное таким образом отношение эквивалентности разбивает все множество целых чисел на два непересекающихся подмножества: подмножество четных чисел и подмножество нечетных чисел.
Обобщая этот случай, будем говорить, что два целых числа, отличающиеся на кратное какого-нибудь фиксированного натурального числа, эквивалентны. На этом основано понятие сравнимости по модулю, введенное Гауссом.
Число а , сравнимо с 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.