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

Числа в основном сравнивают по величине, но их можно сравнивать по другим признакам и свойствам. Например, по количеству цифр, по остаткам деления, по делимости на некоторое число и др.

Рассмотрим сравнение чисел на основе равенства их остатков при делении на некоторое число, что приводи к понятию вычетов. Такое сравнение называется сравнением по модулю. Не следует путать с абсолютной величиной числа, которая так же называется модулем. Введем форму записи остатка:

R = A mod B, где A -делимое, B - делитель, R -остаток.

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

Например, 5=15 mod 10, 3= 45 mod 7 и т.д.

При делении n (" nÎ Z) на g все целые числа разбиваются на g подмножеств, которые соответствуют числу, полученному в остатке. Остатки при этом будут равны:

n mod g ={0, 1, 2, …g-1}

Причем, каждому остатку можно поставить в соответствие множество чисел вида:

0 ® n mod g =0 n=k g

1 ® n mod g =1 n=kg+1

2 ® n mod g =2 n=kg+2

3 ® n mod g =3 n=kg+3

g-1 ® n mod g =g-1 n=k(g-1)

Очевидно, что любое целое число а принадлежит одному из этих g подмножеств. Причем разность любых двух чисел одного под­множества делится на g, а разность чисел из разных множеств не должна делиться на g.

Два целых числа называются сравнимыми по модулю g (g ³ 2), если их разность кратна натуральному числу, т.е. (а - b) g,.

Запишем это определение символами:

а º b (mod g), если $ kÎ Z (а - b= kg).,

Это значит, что числа а и b сравнимы по модулю g тогда и только тогда, когда они принадлежат одному подмножеству, т.е. дают одинаковые остатки при делении на g..

Например: 36 º I6 (mod l0) – числа 36 и 16 сравнимы по модулю 10

24 º 4 (mod 6) - число 24 сравнимо по модулю 6 с число 4

-26º 6 (mod 30)

Отметим разницу в записях: записей:

1. аº b (mod g) или (а= b) (mod g) означает сравнимость чисел по модулю (сравнение)

2. а= b (mod g) - означает равенство числа a остатку от деления b на g

Отношение сравнимости рефлексивно, симметрично, транзитивно. Следовательно, оно является отношением эквивалентности.

Вычетами по модулю р называют отдельные классы эквивалентности для отношения сравнимо­сти (по модулю p)) и обозначают Z_p,

Раздел математики, изучающий вычеты по модулю, называется ал­геброй вычетов (теорией вычетов, модулярной арифметикой).