ПЕРВУШКИН БОРИС НИКОЛАЕВИЧ
ЧОУ «Санкт-Петербургская Школа «Тет-а-Тет»
Учитель Математики Высшей категории
Сравнение чисел по модулю
Определение 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=s1p+r1. Тогда
|
|
|
или
|
|
(2) |
Так как r1 принимает один из чисел 0,1, ..., p−1, то абсолютное значение r1−r меньшеp. Но из (2) следует, что r1−r кратно p. Следовательно r1=r и s1=s.
Число r называется вычетом числа a по модулю p (другими словами, число rназывается остатком от деления числа a на p).
Утверждение 2. Если два числа a и b сравнимы по модулю p, то a−b делится на p.
Действительно. Если два числа a и b сравнимы по модулю p, то они при делении на pимеют один и тот же остаток p. Тогда
|
|
|
где s и s1 некоторые целые числа.
Разность этих чисел
|
|
(3) |
делится на p, т.к. правая часть уравнения (3) делится на p.
Утверждение 3. Если разность двух чисел делится на p, то эти числа сравнимы по модулю p.
Доказательство. Обозначим через r и r1 остатки от деления a и b на p. Тогда
|
|
|
откуда
|
|
|
По утверждению a−b делится на p. Следовательно r−r1 тоже делится на p. Но т.к. r и r1числа 0,1,..., p−1, то абсолютное значение |r−r1|<p. Тогда, для того, чтобы r−r1 делился на p должно выполнятся условие r=r1.
Из утверждения следует, что сравнимые числа - это такие числа, разность которых делится на модуль.
Если нужно записать, что числа 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), |
|
то
|
am≡bn mod (p). |
|
Действительно.Так как a−b делится на p, то (a−b)m также делится на p, следовательно
|
am≡bm mod (p). |
|
Далее m−n делится на p, следовательно b(m−n)=bm−bn также делится на p, значит
|
bm≡bn mod (p). |
|
Таким образом два числа am и bn сравнимы по модулю с одним и тем же числом bm, следовательно они сравнимы между собой (свойство 2).
Свойство 5. Если
|
a≡b mod (p). |
|
то
|
ak≡bk mod (p). |
|
где k некоторое неотрицательное целое число.
Действительно. Имеем a≡b mod (p). Из свойства 4 следует
|
a·a≡b·b mod (p). |
|
|
a·a·a≡b·b·b mod (p). |
|
|
................. |
|
|
ak≡bk mod (p). |
|
Все свойства 1-5 представить в следующем утверждении:
Утверждение 4. Пусть f(x1, x2, x3, ...) целая рациональная функция с целыми коэффициентами и пусть
|
a1≡b1, a2≡b2, a3≡b3, ... mod (p). |
|
тогда
|
f(a1, a2, a3, ...)≡f(b1, b2, b3, ...) mod (p). |
|
При делении все обстоит иначе. Из сравнения
|
am≡bm mod (p) |
|
не всегда следует сравнение
|
a≡b mod (p). |
|
Утверждение 5. Пусть
|
am≡bm mod (p), |
|
тогда
|
a≡b mod (p/λ), |
|
где λ это наибольший общий делитель чисел m и p.
Доказательство. Пусть λ наибольший общий делитель чисел m и p. Тогда
|
m=m1λ и k=k1λ. |
|
Так как m(a−b) делится на k, то
|
|
|
имеет нулевой остаток. Тогда
|
|
|
.Следовательно
|
|
|
имеет нулевой остаток, т.е. m1(a−b) делится на k1. Но числа m1 и k1 числа взаимно простые. Следовательно a−b делится на k1=k/λ и, тогда, a≡b mod (p/λ).
Утверждение 6. Если
|
a≡b mod (p) |
|
и m является один из делителей числа p, то
|
a≡b mod (m). |
|
Действительно. a−b делится на p. p делится на m. Следовательно a−b делится на m.
Утверждение 7. Если
|
a≡b mod (p), a≡b mod (q), a≡b mod (s) |
|
то
|
a≡b mod (h), |
|
где h наименьшее общее кратное чисел 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. Все свойства сравнений остаются в силе и для отрицательных модулей.
