Основы программирования



              

Кольцо вычетов по модулю m - часть 2


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

3%5 = 3, 17%5 = 2, (-3)%5 = -3, (-17)%5 = -2.

При делении на положительное число знак остатка совпадает со знаком делимого. При таком определении тождество

(-a)%b = a%(-b) = -(a%b)

справедливо. Это позволяет во многих алгоритмах не следить за знаками (так же, как в тригонометрии формулы, выведенные для углов, меньших 90 градусов, автоматически оказываются справедливыми для любых углов).

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

0,1,2,3, ...m-1.

Очень удобна также симметричная система остатков, состоящая из отрицательных и неотрицательных чисел, не превосходящих m/2 по абсолютной величине. Пусть

k = целая часть(m/2)

тогда симметричная система остатков при нечетном m состоит из элементов

-k, -k+1, ..., -1, 0, 1, ..., k-1, k,

а при четном m - из элементов

-k, -k+1, ..., -1, 0, 1, ..., k-1.

Например, при m = 5 симметричная система остатков состоит из элементов

-2, -1, 0, 1, 2.

Кольцо Zm можно представлять состоящим из элементов, принадлежащих выбранной системе остатков. Арифметические операции определяются следующим образом: надо взять два остатка, произвести над ними операцию как над обычными целыми числами и выбрать тот остаток, которой лежит в том же классе эквивалентности, что и результат операции. Например, для симметричной системы остатков множества Z5 имеем:

1+1 = 2, 1+2 = -2, 1+(-2) = -1, 1+(-1) = 0, (-2)+2 = 0, (-2)+(-2) = 1.




Содержание  Назад  Вперед