Основное содержание
Информатика
Course: Информатика > Модуль 2
Урок 5: Модульная арифметика- Что такое модульная арифметика?
- Оператор модуля
- Испытание по модульной арифметике
- Равенство по модулю
- Отношение равенства
- Отношения эквивалентности
- Теорема о делимости целых чисел с остатком
- Сложение и вычитание по модулю
- Сложение по модулю
- Испытание по теме «Модульная арифметика» (сложение и вычитание)
- Умножение по модулю
- Умножение по модулю
- Возведение в степень по модулю
- Быстрое возведение в степень по модулю
- Быстрое возведение в степень по модулю
- Обратное число по модулю
- Алгоритм Евклида
Обратное число по модулю
Что такое обратное число?
Как вы помните, если некое число умножить на число, обратное ему, то получится 1. Из основ арифметики мы знаем следующее:
- Числом, обратным к числу A, называется такое число 1/A, что A * 1/A = 1 (то есть, к примеру, для числа 5 обратным будет 1/5).
- У каждого вещественного числа, кроме 0, есть обратное.
- Умножение на число, обратное A, эквивалентно делению на A (то есть, к примеру, 10/5 — это то же, что 10* 1/5).
Что такое обратное число по модулю?
В модульной арифметике нет операции деления, но есть обратные числа.
- Число, обратное A (mod C), обозначается A^-1.
- (A * A^-1) ≡ 1 (mod C) , или, что то же самое, (A * A^-1) mod C = 1.
- Только у чисел, взаимно простых с C (то есть у тех, у которых нет с C общих простых делителей), есть обратные (mod C)
Как найти обратное число по модулю
Самый простой метод нахождения обратного числа к A (mod C) выглядит следующим образом:
Шаг 1. Вычисляем A * B mod C для всех B от 0 до C-1.
Шаг 2. Обратным числом для A mod C будет являться такое B, для которого A * B mod C = 1
Обратите внимание, что B mod C может принимать значения от 0 до C-1, поэтому нет смысла проверять числа, бо́льшие чем B.
Пример: A=3, C=7
Шаг 1. Вычисляем A * B mod C для значений B от 0 до C-1
3 * 0 ≡ 0 (mod 7)
3 * 1 ≡ 3 (mod 7)
3 * 2 ≡ 6 (mod 7)
3 * 3 ≡ 9 ≡ 2 (mod 7)
3 * 4 ≡ 12 ≡ 5 (mod 7)
3 * 5 ≡ 15 (mod 7) ≡ 1 (mod 7) <------ ОБРАТНОЕ НАЙДЕНО!
3 * 6 ≡ 18 (mod 7) ≡ 4 (mod 7)
Шаг 2. Обратным значением для A mod C является такое B, при котором A * B mod C = 1
5 — это обратное значение для 3 mod 7, поскольку 5*3 mod 7 = 1.
Всё просто!
Давайте рассмотрим другой пример, где обратного значения нет.
Пример: A=2, C=6
Шаг 1. Вычисляем A * B mod C для всех B от 0 до C-1**
2 * 0 ≡ 0 (mod 6)
2 * 1 ≡ 2 (mod 6)
2 * 2 ≡ 4 (mod 6)
2 * 3 ≡ 6 ≡ 0 (mod 6)
2 * 4 ≡ 8 ≡ 2 (mod 6)
2 * 5 ≡ 10 ≡ 4 (mod 6)
Шаг 2. Обратным значением для A mod C является такое B, при котором A * B mod C = 1
Таких значений B, при которых A * B mod C = 1, не существует. Следовательно, у числа A нет обратного значения (mod 6).
Всё дело в том, что числа 2 и 6 не являются взаимно простыми (у них есть общий простой делитель 2).
Всё дело в том, что числа 2 и 6 не являются взаимно простыми (у них есть общий простой делитель 2).
Кажется, что этот метод слишком медленный…
Есть более быстрый способ нахождения обратного значения для A (mod C), который мы и обсудим в следующих статьях, посвящённых расширенному алгоритму Евклида.
Хотите присоединиться к обсуждению?
Пока нет ни одной записи.