Полная и приведенная системы вычетов

Доказательство.

Доказательство.

a ≡ b(mod m) ⇔ a=b+mt ⇔ ak=bk+mkt ⇔ ak ≡ bk(mod mk).

Свойство 9. Если сравнение a ≡ b имеет место по нескольким разным модулям, то оно имеет место и по модулю, равному наименьшему общему кратному этих модулей.

Доказательство. Если a ≡ b(mod m ₁) и a ≡ b(mod m ₂), то a-b делится на m ₁ и на m ₂, значит a-b делится на наименьшее общее кратное m ₁ и m ₂.

Свойство 10. Если сравнение имеет место по модулю m, то оно имеет место и по модулю d

, равному любому делителю числа m.

Доказательство очевидно следует из транзитивности отношения делимости: если a ≡ b(mod m), то a-b делится на m, значит a-b делится на d, где d|m.

Свойство 11. Если одна часть сравнения и модуль делятся на некоторое число, то и другая часть сравнения должна делиться на то же число.

a ≡ b(mod m) ⇔ a=b+mt

Пример. Доказать, что при любом натуральном n число 37 n+2 +16 n+1 +23 n делится на 7.

Решение. Очевидно, что 37 ≡ 2(mod 7), 16 ≡ 2(mod 7), 23 ≡ 2(mod 7)

Возведем первое сравнение в степень n+2, второе – в степень n+1, третье – в степень n и сложим:

т.е. 37 n+2 +16 n+1 +23 n делится на 7. Как видите, ровным счетом ничего сложного в решении

подобных школьных задач "повышенной трудности" нет.

С удовольствием заканчиваю настоящий пункт, чтобы устремиться к следующему, то есть

устремиться из прошлого в будущее.

В предыдущем пункте было отмечено, что отношение ≡ 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.

Дата добавления: 2015-05-26