3.9Немного об арифметических операциях по модулю n.

Операция «остаток от деления на n» любому положительному числу сопоставляет число из интервала [0,n-1]. Если взять за исходный некоторый интервал длины n (количество чисел в интервале), то сопоставление будет взаимно однозначным.

Сдвиг этого интервала вправо по числовой оси на n или любое число кратное n приведет нас к интервалу, числа из которого сопоставляется с интервалом [0,n-1] точно таким же образом, что и исходный интервал. То есть операция «остаток от деления» инвариантна относительно смещения вправо на шаг, кратный длине интервала.

При выполнении всех операций по модулю n результат должен оставаться в области неотрицательных чисел, не превышающих n. Будем считать, что исходные числа правильные, то есть из интервала [0,n-1]. При выполнении арифметических операций промежуточный или конечный результат могут получиться в диапазоне [–(n-1),(n-1)²]. В этом случае применяется операция вычисления остатка от деления на n, возможно дополненная сдвигом вправо по числовой оси на число, кратное n.