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

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

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

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

Определение 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 . Все свойства сравнений остаются в силе и для отрицательных модулей.

Обозначим на координатной прямой две точки, которые соответствуют числам −4 и 2.

Точка A, соответствующая числу −4, находится на расстоянии 4 единичных отрезков от точки 0 (начала отсчёта), то есть длина отрезка OA равна 4 единицам.

Число 4 (длина отрезка OA) называют модулем числа −4.

Обозначают модуль числа так: |−4| = 4

Читают символы выше следующим образом: «модуль числа минус четыре равен четырём».

Точка B, соответствующая числу +2, находится на расстоянии двух единичных отрезков от начала отсчёта, то есть длина отрезка OB равна двум единицам.

Число 2 называют модулем числа +2 и записывают: |+2| = 2 или |2| = 2.

Если взять некоторое число «a» и изобразить его точкой A на координатной прямой, то расстояние от точки A до начала отсчёта (другими словами длина отрезка OA) и будет называться модулем числа «a».

Запомните

Модулем рационального числа называют расстояние от начала отсчётадо точки координатной прямой, соответствующей этому числу.

Так как расстояние (длина отрезка) может выражаться только положительным числом или нулём, можно сказать, что модуль числа не может быть отрицательным.

Запомните

Запишем свойства модуля с помощью буквенных выражений,рассмотрев

все возможные случаи.

1. Модуль положительного числа равен самому числу. |a| = a, если a > 0;

2. Модуль отрицательного числа равен противоположному числу. |−a| = a, если a < 0;

3. Модуль нуля равен нулю. |0| = 0, если a = 0;

4. Противоположные числа имеют равные модули.

Примеры модулей рациональных чисел:

· |−4,8| = 4,8

· |0| = 0

· |−3/8| = |3/8|

Из двух чисел на координатной прямой больше то, которое расположено правее, а меньше то, которое расположено левее.

Запомните

· любое положительное число больше нуля и больше любого

отрицательного числа;

· любое отрицательное число меньше нуля и меньше любого

положительного числа.

Пример.

Сравнивать рациональные числа удобно с помощью понятия модуля .

Большее из двух положительных чисел изображается точкой, расположенной на координатной прямой правее, то есть дальше от начала отсчёта. Значит, это число имеет больший модуль.

Запомните

Из двух положительных чисел больше то, чей модуль больше.

При сравнении двух отрицательных чисел большее будет расположено правее, то есть ближе к началу отсчёта. Значит, его модуль (длина отрезка от нуля до числа) будет меньше.

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

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

Число а , сравнимо с 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.