АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Свойства арифметики в классах вычетов

Читайте также:
  1. АК. Структура белков, физико-химические свойства (192 вопроса)
  2. Активные минеральные добавки. Смешанные цементы, их свойства.
  3. Анализ свойства вязкости
  4. Антигены, основные свойства. Антигены гистосовместимости. Процессинг антигенов.
  5. Арифметическая середина и ее свойства.
  6. Арифметические операции над последовательностями. Свойства пределов, связанные с арифметическими операциями над последовательностями.
  7. Биохимические свойства.
  8. Бытовые часы. классификация ассортимента и потребительские свойства.
  9. В 1. Строение и свойства, особенности сварки алюминиевых сплавов.
  10. В 1. Шлаковая фаза, ее образование при дуговой сварке. Основные физические свойства шлаков и их влияние на процесс сварки.
  11. В 4. Характеристика процесса горения. Виды горения. Горючие вещества Взрывопожароопасные свойства ГВ.
  12. Виды и свойства внимания

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

Пусть 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, то bc mod n.

 

(5 + 23) ≡ (5 + 7) mod 8; 23 ≡ 7 mod 8.

Продолжение приложения 1

 

Данное свойство согласуется с существованием аддитивного обратного. Прибавив к обеим частям данного равенства аддитивное обратное элемента а, получим:

((- a) + a + b) ≡ ((- a) + a + c) mod n, bc mod n.

 

Однако следующее утверждение выполняется только при указанном условии:

если (a * b) ≡ (a * c) mod n, то bc 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,
bc mod n.

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)