3 Сравнения и арифметика остатков
Определение. Пусть а, b ??Z , m ??N . Говорят, что число а сравнимо с b по модулю m , если а и b при делении на m дают одинаковые остатки. Запись этого факта выглядит так:
a ??b(mod m) .
Очевидно, что бинарное отношение сравнимости ??m (неважно, по какому модулю) есть отношение эквивалентности на множестве целых чисел, а любители алгебры скажут, что это отношение является даже конгруэнцией кольца Z , фактор-кольцо по которой Z/ ??m называется кольцом вычетов и обозначается Z m .
Ясно, что число a сравнимо с b по модулю m тогда и только тогда, когда a-b делится на m нацело. Очевидно, это, в свою очередь, бывает тогда и только тогда, когда найдется такое целое число t , что a=b+mt . Знатоки алгебры добавят к этим эквивалентным утверждениям, что сравнимость a с b по модулю m означает, что a и b представляют один и тот же элемент в кольце Z m .
Свойство 1. Сравнения по одинаковому модулю можно почленно складывать.
Доказательство. Пусть a1??b1(mod m), a2??b2(mod m). Это означает, что a 1 =b 1 +mt 1 , a 2 =b 2 +mt 2 . После сложения последних двух равенств получим a 1 +a 2 =b 1 +b 2 +m(t 1 +t 2 ) , что означает a 1 +a 2 ??b 1 +b 2 (mod m).
Свойство 2. Слагаемое, стоящее в какой-либо части сравнения, можно переносить в другую часть, изменив его знак на обратный.
Доказательство.
Свойство 3. К любой части сравнения можно прибавить любое число, кратное модулю.
Доказательство.
?
Свойство 4. Сравнения по одинаковому модулю можно почленно перемножать и, следовательно,
Свойство 5. Обе части сравнения можно возвести в одну и ту же степень.
Доказательство.
?
Как следствие из вышеперечисленных свойств, получаем
Свойство 6. Если
a 0 ??b 0 (mod m) , a 1 ??b 1 (mod m) ,..., a n ??b n (mod m) , x ??y(mod m) ,
то a 0 x n +a 1 x n-1 +...+a n ??b 0 y n +b 1 y n-1 +...+b n (mod m)
Свойство 7. Обе части сравнения можно разделить на их общий делитель, взаимно простой с модулем.
Доказательство. Пусть a ??b(mod m) , a=a 1 d , b=b 1 d . Тогда (a 1 -b 1 ) ??d делится на m . Поскольку d и m взаимно просты, то на m делится именно (a 1 -b 1 ) , что означает a 1 ??b 1 (mod m) .
?
Свойство 8. Обе части сравнения и его модуль можно умножить на одно и то же целое число или разделить на их общий делитель.
Доказательство.
a ??b(mod m) ??a=b+mt ??ak=bk+mkt ??ak ??bk(mod mk) .
?
Свойство 9. Если сравнение a ??b имеет место по нескольким разным модулям, то оно имеет место и по модулю, равному наименьшему общему кратному этих модулей.
Доказательство. Если a ??b(mod m 1 ) и a ??b(mod m 2 ) , то a-b делится на m 1 и на m 2 , значит a-b делится на наименьшее общее кратное m 1 и m 2 .
Свойство 10. Если сравнение имеет место по модулю m , то оно имеет место и по модулю d , равному любому делителю числа m .
Доказательство очевидно следует из транзитивности отношения делимости: если a ??b(mod m) , то a-b делится на m , значит a-b делится на d , где d|m .
?
Свойство 11. Если одна часть сравнения и модуль делятся на некоторое число, то и другая часть сравнения должна делиться на то же число.
Доказательство.
a ??b(mod m) ??a=b+mt .
?
Отношение ??m сравнимости по произвольному модулю m есть отношение эквивалентности на множестве целых чисел. Это отношение эквивалентности индуцирует разбиение множества целых чисел на классы эквивалентных между собой элементов, т.е. в один класс объединяются числа, дающие при делении на m одинаковые остатки. Число классов эквивалентности ??m (знатоки скажут - "индекс эквивалентности ??m ") в точности равно m .
Определение. Любое число из класса эквивалентности ??m будем называть вычетом по модулю m . Совокупность вычетов, взятых по одному из каждого класса эквивалентности ??m , называется полной системой вычетов по модулю m (в полной системе вычетов, таким образом, всего m штук чисел). Непосредственно сами остатки при делении на m называются наименьшими неотрицательными вычетами и, конечно, образуют полную систему вычетов по модулю m . Вычет ??называется абсолютно наименьшим, если ????наименьший среди модулей вычетов данного класса.
Пример : Пусть m = 5 . Тогда:
0, 1, 2, 3, 4 - наименьшие неотрицательные вычеты;
-2, -1, 0, 1, 2 - абсолютно наименьшие вычеты.
Обе приведенные совокупности чисел образуют полные системы вычетов по модулю 5 .
Лемма 1. 1) Любые m штук попарно не сравнимых по модулю m чисел образуют полную систему вычетов по модулю m .
2) Если а и m взаимно просты, а x пробегает полную систему вычетов по модулю m , то значения линейной формы аx+b , где b - любое целое число, тоже пробегают полную систему вычетов по модулю m .
Доказательство. Утверждение 1) - очевидно. Докажем утверждение 2). Чисел аx+b ровно m штук. Покажем, что они между собой не сравнимы по модулю m . Ну пусть для некоторых различных x 1 и x 2 из полной системы вычетов оказалось, что ax 1 +b ??ax 2 +b(mod m) . Тогда, по свойствам сравнений из предыдущего пункта, получаем:
ax 1 ??ax 2 (mod m)
x 1 ??x 2 (mod m)
- противоречие с тем, что x 1 и x 2 различны и взяты из полной системы вычетов.
Поскольку все числа из данного класса эквивалентности ??получаются из одного числа данного класса прибавлением числа, кратного m , то все числа из данного класса имеют с модулем m один и тот же наибольший общий делитель. По некоторым соображениям, повышенный интерес представляют те вычеты, которые имеют с модулем m наибольший общий делитель, равный единице, т.е. вычеты, которые взаимно просты с модулем.
Определение. Приведенной системой вычетов по модулю m называется совокупность всех вычетов из полной системы, взаимно простых с модулем m .
Приведенную систему обычно выбирают из наименьших неотрицательных вычетов. Ясно, что приведенная система вычетов по модулю m содержит ??( m ) штук вычетов, где ??( m )- функция Эйлера - число чисел, меньших m и взаимно простых с m . Если к этому моменту вы уже забыли функцию Эйлера, загляните в пункт 14 и убедитесь, что про нее там кое-что говорилось.
Пример. Пусть m = 42. Тогда приведенная система вычетов суть:
1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41.
Лемма 2. 1) Любые ??( m ) чисел, попарно не сравнимые по модулю m и взаимно простые с модулем, образуют приведенную систему вычетов по модулю m .
2) Если ( a,m ) = 1 и x пробегает приведенную систему вычетов по модулю m , то аx так же пробегает приведенную систему вычетов по модулю m .
Доказательство. Утверждение 1) - очевидно. Докажем утверждение 2). Числа аx попарно несравнимы (это доказывается так же, как в лемме 1 этого пункта), их ровно ??( m ) штук. Ясно также, что все они взаимно просты с модулем, ибо (a,m)=1, (x,m)=1 ??(ax.m)=1 . Значит, числа аx образуют приведенную систему вычетов.