КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Вычисление обратных величин
В арифметике действительных чисел нетрудно вычислить мультипликативную обратную величину а–1 для ненулевого а:
а –1 = 1 / а или а • а –1 = 1.
Пример: мультипликативная обратная величина от числа 4 равна 1 / 4, поскольку 4 • 1 / 4 = 1.
В модулярной арифметике вычисление обратной величины является более сложной задачей. Например, решение сравнения
4 • х ≡ 1 (mod 7)
эквивалентно нахождению таких значений х и k, что
4 • х ≡ 7 • k + 1,
где х и k – целые числа.
Общая формулировка этой задачи – нахождение такого целого числа х такого, что а • х (mod n) = 1.
Можно также записать а –1 ≡ х (mod n). Решение этой задачи иногда существует, а иногда его нет. Например, обратная величина для числа 5 по модулю 14 равна 3, т.к.
5 • 3 = 15 ≡ 1 (mod 14).
С другой стороны, число 2 не имеет обратной величины по модулю 14. Вообще сравнение а –1 ≡ х (mod n) имеет единственное решение, если а и n – взаимно простые числа. Если числа а и n – не являются взаимно простыми, тогда сравнение Сформулируем основные способы нахождения обратных величин. Пусть целое число а Î {0, 1, 2, …, n - 1}. Если НОД (а, n) = 1, то а • i (mod n) при i = 0, 1, 2, …, n – 1 является перестановкой множества {0, 1, 2, …, n - 1}. Пример. Если а = 3 и n = 7 (НОД (3, 7) = 1), то 3 • i (mod 7) при i = 0, 1, 2, …, 6 является последовательностью 0, 3, 6, 2, 5, 1, 4, т.е. перестановкой множества {0, 1, 2, …, 6}.
Это будет неверным, когда НОД (а, n) ¹ 1.
Пример. Если а = 2 и n = 6, то 2 • i (mod 6) º 0, 2, 4, 0, 2, 4 при i = 0, 1, 2, …, 5.
Если НОД (а, n) = 1, тогда существует обратное число а–1, а • а –1 º 1 (mod n).
Действительно, а • i (mod n) является перестановкой 0, 1, 2, …, n – 1, поэтому существует i такое, что
а • i º 1 (mod n).
Как отмечалось выше, набор целых чисел от 0 до n – 1 называется полным набором вычетов по модулю n. Это означает, что для любого целого числа а (а > 0) его вычет r = a (mod n) – это некоторое целое число в интервале от 0 до n – 1. Выделим из полного набора вычетов подмножество вычетов взаимно простых с n. Такое подмножество называют приведенным набором вычетов.
Пример. Пусть модуль n = 11 – простое число. Полный набор вычетов по модулю 11: {0, 1, 2, …, 10}. При формировании приведенного набора вычетов из них удаляется только один элемент: 0. Приведенный набор вычетов по модулю 11 имеет 11 – 1 = 10 элементов.
Таким образом, в общем случае приведенный набор вычетов по модулю простого числа n имеет n – 1 элемент. Пример. Пусть модуль n = 10. Полный набор вычетов по модулю 10: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Из них только 1, 3, 7, 9 не имеют общего сомножителя с числом 10. Поэтому приведенный набор вычетов по модулю 10 равен {1, 3, 7, 9}. При формировании этого приведенного набора были исключены элементы:
т.е. всего шесть элементов. Вычитая их из 10, получаем 10 – 6 = 4. Таким образом, в приведенном наборе вычетов четыре элемента.
Для произведения простых чисел p • q = n приведенный набор вычетов имеет ( p – 1) • (q – 1) элементов. Пример. При n = p • q = 2 • 5 = 10 число элементов в приведенном наборе будет (p – 1) • (q – 1) = (2 – 1) • (5 – 1) = 4.
Пример. Приведенный набор вычетов по модулю 27 = 3 3 имеет 18 элементов: {1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26}. Из полного набора вычетов исключены элементы, кратные 3 (всего девять элементов).
Отсюда: Для модуля в виде простой степени n r приведенный набор вычетов имеет n r – 1 • (n – 1) элемент. При n = 3, r = 3 получаем 3 3 –1 • (3 – 1) = 3 2 • 2 = 18 элементов.
Число элементов в приведенном наборе вычетов характеризует функция Эйлера j(n).
Таблица 5.1 – Функция Эйлера j(n)
Иначе говоря, функция j(n) – это количество положительных целых, меньших n, которые взаимно просты с n.
Малая теорема Ферма: если n – простое и НОД (а, n) = 1, то а n – 1 º 1 (mod n).
Согласно обобщению Эйлером малой теоремы Ферма имеем: если НОД (а, n) = 1, то а j(n) º 1 (mod n).
Если n – простое число, то предыдущий результат, учитывая, что j(n) = n – 1, приводится к виду (малой теоремы Ферма)
а n – 1 º 1 (mod n).
Дата добавления: 2015-08-31; Просмотров: 2415; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |