ПЕРВУШКИН БОРИС НИКОЛАЕВИЧ

ЧОУ «Санкт-Петербургская Школа «Тет-а-Тет»

Учитель Математики Высшей категории

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

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