Что такое обратное число?
Как вы помните, если некое число умножить на число, обратное ему, то получится 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 * 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. Обратным значением для A mod C является такое B, при котором A * B mod C = 1
Таких значений B, при которых A * B mod C = 1, не существует. Следовательно, у числа A нет обратного значения (mod 6).
Всё дело в том, что числа 2 и 6 не являются взаимно простыми (у них есть общий простой делитель 2).
Кажется, что этот метод слишком медленный…
Есть более быстрый способ нахождения обратного значения для A (mod C), который мы и обсудим в следующих статьях, посвящённых расширенному алгоритму Евклида.
-
Вычисление обратных величин
В
арифметике дествительных чисел нетрудно
вычислить мультипликативную обратную
величину а–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
– не являются взаимно простыми, тогда
сравнение
а –1 ≡ х (mod
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,
0 < а –1
< n, такое, что
а • а –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}. При формировании этого
приведенного набора были исключены
элементы:
|
0 |
(один элемент), |
|
кратные 2 |
(четыре элемента), |
|
кратные 5 |
(один элемент), |
т.е. всего шесть
элементов. Вычитая их из 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 элементов.
Число
элементов в приведенном наборе вычетов
характеризует функция Эйлера
(n).
Таблица
1.3.1 – Функция Эйлера (n)
|
Модуль n |
Функция (n) |
|
n n 2 . . . n |
n – 1 n • . . . n |
|
p • q . . . . . .
|
(p – 1) . . . . . .
|
i
i
Иначе
говоря, функция (n)
– это количество положительных целых,
меньших n,
которые взаимно просты с n.
Малая
теорема Ферма:
если n
– простое и НОД (а, n)
= 1, то
а
n
– 1
1 (mod
n).
Согласно
обобщению Эйлером
малой теоремы Ферма имеем: если НОД
(а, n)
= 1, то
а
(n)
1 (mod
n).
Если
n – простое число, то
предыдущий результат, учитывая, что
(n)
= n – 1, приводится к виду
(малой теоремы Ферма)
а
n
– 1
1 (mod
n).
Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]
- #
- #
- #
- #
- #
- #
- #
- #
- #
- #
- #
Обратный по модулю
❓Инструкция
Калькулятор онлайн для вычисления обратного элемента по модулю в кольце. Алгоритм поддерживает работу с большими числами с некоторыми ограничениями.
Использование:
Заполняются два поля — число a и модуль m. Число a — число к которому ищем обратный, m — модуль, по которому ищем.
Калькулятор выдает обратный элемент после нажатия на кнопку «Вычислить».
Если установлена галочка «подробнее», то калькулятор помимо обратного элемента по модулю выдает некоторые этапы вычисления.
Ограничения:
Калькулятор поддерживает работу с большими целыми числами (в том числе отрицательными числами для числа a, и только положительными для модулю m) длиной не более 10 000 символов.
📖 Теория
Что значит по модулю?
Синонимом к данному выражению является выражение «остаток от деления«. То есть выражение «5 по модулю 3» эквивалентно выражению «остаток от деления 5 на 3». И в том и в другом случае подразумевается в ответе число 2, так как остаток от деления 5 на 3 = 2.
Стоить отметить тот факт, что по модулю m мы имеем числа от 0 до m — 1. Действительно, остаток от деления на m никогда не превысит m — 1.
Что такое обратное?
Напомним, что число, умноженное на его обратное, равно 1. Из базовой арифметики мы знаем, что:
Число, обратное к числу A, равно 1 / A, поскольку A * (1 / A) = 1 (например, значение, обратное к 5, равно 1/5). Все действительные числа, кроме 0, имеют обратную Умножение числа на обратное к A эквивалентно делению на A (например, 10/5 соответствует 10 * 1/5)
Что такое обратное по модулю?
В модульной арифметике у нас нет операции деления. Тем не менее, у нас есть модульные инверсии.
Модульная инверсия a (mod m) есть a-1 (a * a-1) ≡ 1 (mod m) или эквивалентно (a * a-1) mod m = 1 Только числа, взаимно простые с модулем m, имеют модульное обратное.
Говоря проще, обратным элементом к a по модулю m является такое число b, что остаток от деления (a * b) на модуль m равно единице (a * a-1) mod m = 1
Как найти модульный обратный
Наивный метод нахождения модульного обратного a ( по модулю m) является:
Шаг 1. Рассчитать a * b mod m для значений b от 0 до m — 1
Шаг 2. Модульная инверсия a mod m — это значение b, при котором a * b mod m = 1
Обратите внимание, что термин b mod m может иметь только целочисленное значение от 0 до m — 1, поэтому тестирование больших значений чем (m-1) для b является излишним.
Вы наверно уже догадались, что наивный метод является очень медленным. Перебор всех чисел от 0 до m-1 для большого модуля довольно-таки трудоемкая задача. Существует гораздо более быстрый метод нахождения инверсии a (mod m). Таковым является расширенный алгоритм Евклида, который реализован в данном калькуляторе.
Расширенный алгоритм Евклида
Представим наибольший общий делитель числа a и модуля m в виде ax + my. То есть НОД(a, m) = ax + my. Помним, что обратный элемент существует только тогда, когда a и m взаимно просты, то есть их НОД(a, m) = 1. Отсюда: ax + my = 1 — линейное диофантово уравнение второго порядка. Необходимо решить данное уравнение в целых числах и найти x, y.
Найденный коэффициент x будет являться обратным элементом к a по модулю m. Это следует оттуда, что, если мы возьмём от обеих частей уравнения остаток по модулю m, то получим: ax = 1 (m).
Расширенный алгоритм Евклида, в отличие от классического, помимо наибольшего общего делителя позволяет найти также коэффициенты x, y.
Алгоритм:
Вход: a, m ≠ 0
Выход: d, x, y, такие что d = gcd(a, m) = ax + my
1. [Инициализация] (a0, a1) := (a, m); (x0, x1) := (1, 0); (y0; y1) := (0, 1).
2. [Основной цикл] Пока a1 ≠ 0 выполнять {q = QUO(a0, a1);
(a0, a1) := (a1, a0 — a1q); (x0, x1) := (x1, x0 — x1q); (y0, y1) := (y1, y0 — y1q);
QUO(a0, a1) — целая часть от деления a0 на a1
3. [Выход] Вернуть (d, x, y) = (a0, x0, y0)
Битовая сложность расширенного алгоритма Евклида равна O((log2(n))2) , где n = max (|a|, |m|)
Непонятен алгоритм? Ничего страшного, примеры ниже именно для этого и предназначены.
➕ Примеры
Пример для наивного метода.
Пусть a = 3, m = 7. То есть нам необходимо найти обратный элемент к 3 по модулю 7.
Шаг 1. Рассчитать a * b mod m для значений B от 0 до m-1. По очереди проверяем числа от 0 до 6.
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)
при b = 5 выполнилось условие, что a * b ≡ 1 (m). Следовательно, b = 5 является обратным элементом к 3 по модулю 7.
Пример на расширенный алгоритм Евклида.
Пусть аналогично предыдущему примеру имеем a = 3, m = 7. Также, требуется найти обратный элемент к 3 по модулю 7. Согласно алгоритму начинаем заполнять таблицу на каждом этапе цикла.
| Итерация | q | a0 | a1 | x0 | x1 | y0 | y1 |
| 0 | — | 3 | 7 | 1 | 0 | 0 | 1 |
| 1 | 0 | 7 | 3 | 0 | 1 | 1 | 0 |
| 2 | 2 | 3 | 1 | 1 | -2 | 0 | 1 |
| 3 | 3 | 1 | 0 | -2 | 0 | 1 | -3 |
После 3-ей итерации получили a1 = 0, строго по алгоритму из раздела «Теория» заканчиваем работу алгоритма.
(d, x, y) = (a0, x0, y0)
(d, x, y) = (1, -2, 1), видим, что d = НОД(3, 7) = 1, следовательно числа 3 и 7 являются взаимно простыми, а значит обратный существует.
Делаем проверку:
3 * (-2) + 7 * 1 = 1
-6 + 7 = 1
1 = 1 — верно!
Обратным элементом к тройке по модулю 7 является x = -2. По модулю 7 число -2 равно 5. Получили, что x = 5 является обратным элементом к 3 по модулю 7.
Калькулятор для вычисления обратного элемента по модулю ниже, теория под ним.
Обратный элемент в кольце по модулю
Обратным к числу a по модулю m называется такое число b, что:
,
Обратный элемент обозначают как .
Для нуля обратного элемента не существует никогда, для остальных же элементов обратный элемент может как существовать, так и нет.
Утверждается, что обратный элемент существует только для тех элементов a, которые взаимно просты с модулем m.
Для нахождения обратного элемента по модулю можно использовать Расширенный алгоритм Евклида.
Для того, чтобы показать это, рассмотрим следующее уравнение:
Это линейное диофантово уравнение с двумя переменными, см. Линейные диофантовы уравнения с двумя переменными. Посколько единица может делиться только на единицу, то уравнение имеет решение только если .
Решение можно найти с помощью расширенного алгоритма Евклида. При этом, если мы возьмём от обеих частей уравнения остаток по модулю m, то получим:
Таким образом, найденное x и будет являться обратным к a.
There are many methods available, e.g. the extended Euclidean algorithm, $ $ or a special case of Euclid’s algorithm that computes inverses modulo primes that I call Gauss’s algorithm. $ $
The calculations are usually simpler using modular fraction arithmetic e.g. see here, and here and here for circa $20$ motley worked examples via a handful of methods (and see the sidebar «Linked» questions lists there for many more).
Update $ $ March $16, 2020!:,$ for completeness we apply some of the linked methods below.
$!!bmod 31!:, dfrac{1}{7}equiv dfrac{4}{28}equivdfrac{-27}{-3}equiv 9 $ by Gauss’s algorithm.
$!!bmod 31!:, dfrac{1}{7}equiv dfrac{1}{-6},dfrac{1}{4}equiv dfrac{-30}{-6},dfrac{32}{4}equiv 5cdot 8equiv 9$
As here: $ $ the freedom to choose $rmcolor{#c00}{even}$ residue reps $!bmod!$ odds makes division by 2 easy:
$!!bmod 31!:, dfrac{1}{7}equivdfrac{color{#c00}{32}}{color{#c00}{-24}}equivdfrac{4}{-3}equivdfrac{-27}{-3}equiv 9$
By the fractional extended Euclidean algorithm, or associated equational form
$ begin{align} bmod 31!: dfrac{0}{31}overset{largefrown}equivcolor{#c00}{dfrac{1}7} , &!!!overset{largefrown}equivcolor{#0a0}{dfrac{-4}3}overset{largefrown}equivcolor{#90f}{dfrac{9}1}\[.7em]
text{said equationally}
[![1]!] 31, x&,equiv 0 \
[![2]!] color{#c00}{7,x}& color{#c00}{ equiv 1}!!!\
[![1]!]-4,[![2]!] rightarrow [![3]!] color{#0a0}{3,x} & color{#0a0}{equiv {-}4} \
[![2]!] — 2,[![3]!] rightarrow [![4]!], color{#90f}{x}& color{#90f}{ equiv 9}
end{align}$
Below we explain the basic idea behind the method of Inverse Reciprocity.
$!!bmod 31!:, n equiv dfrac{1}7equiv dfrac{1+31color{#c00}k}7. $ For an exact quotient we seek $,k,$ with $,7mid 1!+!31k,,$ i.e.
$!!bmod 7!:, begin{align}0&equiv 1!+!31k\ &equiv 1 + 3kend{align}!$ $iff! begin{align}3k&equiv-1\ &equiv, 6end{align}!$ $iff color{#c00}{kequiv 2}, $ so $ n equiv dfrac{1!+!31(color{#c00}2)}7equiv 9pmod{!31}$
Or $ $ by Euler $rm (a,m)=1 Rightarrow a^{-1} equiv a^{phi(m)-1}pmod{! m},,$ quickly computable by repeated squaring.
Remark $ $ The latter yields a simple closed form for CRT (Chinese Remainder Theorem)
$quad$ if $rm, (m,n)=1, $ then $rmquad begin{eqnarray}rm x!&equiv&rm a (mod m)\ rm x!&equiv&rm b (mod n)end{eqnarray} iff xequiv a,n^{phi(m)}!+b,m^{phi(n)} (mod mn)$
More generally see the Peirce decomposition.