 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Свойства арифметики в классах вычетов
Модулярная арифметика («арифметика часов») аналогична во многом обычной арифметике: она коммутативна, ассоциативна и дистрибутивна.
Пусть Zn обозначает множество всех неотрицательных целых чисел, которые меньше n (полный набор вычетов):
Zn = {0, 1, 2,..., (n - 1)}.
Для арифметических операций по модулю n в этом множестве выполняются следующие свойства:
| Свойство | Выражение |
| Коммутативные законы | (w + x) mod n = (x + w) mod n, (w * x) mod n = (x * w) mod n |
| Ассоциативные законы | [(w + x) + y ] mod n = [ w + (x + y)] mod n, [(w * x) * y ] mod n = [ w * (x * y)] mod n |
| Дистрибутивный закон | [(w + x) * y ] mod n = [(w * y) + (x * y)] mod n |
| Тождества | (0 + w) mod n = w mod n, (1 * x) mod n = w mod n |
| Аддитивный обратный (- w) | Для любого w Î Zn существует такое z, что w + z ≡ 0 mod n |
Существует одна особенность арифметики в классах вычетов, которая делает её отличной от обычной арифметики. Заметим сначала, что, как и в обычной арифметике, имеет место следующее свойство
если (a + b) ≡ (a + c) mod n, то b ≡ c mod n.
(5 + 23) ≡ (5 + 7) mod 8; 23 ≡ 7 mod 8.
Продолжение приложения 1
Данное свойство согласуется с существованием аддитивного обратного. Прибавив к обеим частям данного равенства аддитивное обратное элемента а, получим:
((- a) + a + b) ≡ ((- a) + a + c) mod n, b ≡ c mod n.
Однако следующее утверждение выполняется только при указанном условии:
если (a * b) ≡ (a * c) mod n, то b ≡ c mod n
при условии, что a и n взаимно просты.
Рассмотрим пример, когда условие не выполняется:
6 * 3 = 18 ≡ 2 mod 8,
6 * 7 = 42 ≡ 2 mod 8.
Но 3 ≠ 7 mod 8.
Причиной такого странного результата является то, что для произвольного модуля сравнения n в результате умножения чисел от 0 до (n - 1) на множитель a не получается полного набора всех вычетов, когда a и n имеют общие множители.
При a = 6 и n = 8 имеем:
| Z8 | ||||||||
| Умноженное на 6 | ||||||||
| Остаток |
Поскольку мы не получаем в данном случае полного набора вычетов после умножения на 6, то в один класс вычетов отображается более одного элемента Z8. В частности, 6 * 0 mod 8 = 6 * 4 mod 8. Таким образом, поскольку при данном отображении несколько элементов переводится в один, операция умножения не предпологает существования единственного обратного.
При a =5 и n = 8 имеем:
| Z8 | ||||||||
| Умноженное на 5 | ||||||||
| Остаток |
Теперь строка остатков содержит все возможные значения из класса Z8, но в ином порядке.
Наконец заметим, что если p является простым, то все элементы Zp будут взаимно простыми с p. Это даёт нам возможность добавить ещё одно свойство к тем, которые были приведены выше:
| Свойство | Выражение |
| Мультипликативный обратный (w -1) | Для любого w Î Zp существует z, что w * z ≡ 1 mod p |
В связи с тем что w и p являются взаимно простыми, при умножении каждого элемента Zp на w будет получен набор всех элементов множества Zp в несколько изменённом порядке. Поэтому по крайней мере один из остатков будет иметь значение 1. Таким образом, найдётся некоторое значение в Zp, при умножении которого на w получится значение 1. Это число и будет мультипликативным обратным для w, обозначаемым w -1.
((a -1) * a * b) ≡ ((a -1) * a * c) mod n,
b ≡ c mod n.
Поиск по сайту: