Свойства целочисленных операций с modN

Любые целые числа сравниваются по модулю Nотображением их на множество модуляNравное {0, 1, 2,….N– 1} (1)

Для неотрицательных чисел а 0 отображение их на множество модуля получается циклическим вычитанием из ‘a’ величиныNдо тех пор пока не получится результатr, принадлежащий множеству модуля. Этот результат и есть число ‘a’ представленное (взятое) по модулюN

r=amodN(2)

Если a<N, тоr=a. Произошло отображение ‘a’ на самое себя.

Для отрицательных целых чисел a< 0 отображение на множество модуля распространяется путем циклического прибавленияNк а.

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

Рисунок 3.8

Легко видеть, что для неотрицательных чисел величина rесть остаток от целочисленного делителя ‘a’ наN.

В языке Pascalесть операцияmod– целый остаток от деления двух целых положи тельных чисел.

Понятия amod(-N) не существует, а взять отрицательное целое по модулюNможно так:

(-9)mod4 = - (9mod4) + 4 =-1 + 4 = 3 (3)

Можно и воспользоваться функцией Int(x) – целое число

Для а > 0 r = a mod N = a – N * Int(a/N) (4)

Для a < 0 r = a mod N = a + N * (Int(a/N)+1)

Например:

r = 9 mod 4 = 9 – 4 * Int(9/4) = 9 – 4*2 = 9 – 8 = 1

r = –9 mod 4 = –9 + 4 * (Int(+9/4) = - 9 + 4*(2+1) = 3

В теории чисел определено отношение() сравнимости целых чисел:

ab(modN) (5)

‘a’ сравнимо с ‘b‘ по модулюN, ‘a‘ и ‘b‘ – целые,N0, если только выполняется равенствоa=b+k*N

Еще говорят: Nделит (a–b):N| (a-b) и ‘b’ называютвычетомчисла ‘a' по модулюN.

Выражение (5) равносильно утверждению, что остатки от делений ‘a‘ и ‘b’ наNравны

17 5 (mod12)

означает, что

17 mod12 = 5

5 mod12 = 5

Для N= 12 полный набор вычетов есть {0, 1, 2, … 11}

Выражение a1 (modN) определяет все целые положительные ‘a’, остатки от деления которых наNравны 1.