If you're seeing this message, it means we're having trouble loading external resources on our website.

Если вы используете веб-фильтр, пожалуйста, убедитесь, что домены *.kastatic.org и *.kasandbox.org разблокированы.

Основное содержание

Обратное число по модулю

Что такое обратное число?

Как вы помните, если некое число умножить на число, обратное ему, то получится 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).

Кажется, что этот метод слишком медленный…

Есть более быстрый способ нахождения обратного значения для A (mod C), который мы и обсудим в следующих статьях, посвящённых расширенному алгоритму Евклида.

Хотите присоединиться к обсуждению?

Пока нет ни одной записи.
Знаете английский? Нажмите здесь, чтобы увидеть обсуждение, которое происходит на английской версии сайта.