Сравнимость по модулю. Модулярная арифметика

 

 

Понятие «модулярная арифметика» ввел немецкий ученый Гаусс.

 

Модульная арифметика аналогична обычной арифметике: она коммутативна, ассоциативна и дистрибутивна.

Под операцией a mod m понимается операция взятия целочисленного остатка от деления числа a на число m, где a и m - целые числа.

Запись в модульной арифметике

 

a ≡ b mod m

читается как "a сравнимо с b по модулю m". С помощью знака равенства эту операцию можно записать как

 

a = b + k·m,

 

где a, b, m - целые числа, m ≠ 0, k - некоторое целое число.

 

Отсюда следует, что m делит (a - b) нацело:

 

m | (a - b) или (a - b) mod m = 0.

 

Число b называют вычетом числа a по модулю m.

 

Операция a mod m называется приведением числа a по модулю m или

 

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

 

Пример 1.7. Вычислить (3+14) mod 12.

 

Получим (3+14) mod 12 = 17 mod 12 ≡ 5 или 17 ≡ 5 mod 12. То есть число 5 является вычетом числа 17 по модулю 12.

Ряд целых чисел от 0 до (m - 1) называется полным набором вычетов по модулю m. Для любого целого a (a > 0) его вычет r по модулю m

 

принадлежит интервалу системы

r = 0, m - 1. Число r можно найти перебором из

 

ìr =a -k ×m

ï

í k ÎZ ,

ï

 

перебирая все значения k.

îr =0, m -1

 

Например, для m = 13 полный набор вычетов равен

0, 12 . Но можно

 

11

использовать вычеты и в диапазоне целых чисел

r =-2 (m -1), 2 (m -1) .

 

Если приводимое число является отрицательным, то выполняется его сложение с модулем m. Например, -5 mod 7 = (-5 + 7) mod 7 ≡ 2 mod 7.

 

Достоинствами вычислений по модулю является следующее:

 

- ограничивается диапазон промежуточных величин и результата;

 

- не требуется хранить большие промежуточные результаты.