Пусть даны группы $%A$% и $%B$%, где $%B$% действует на $%A$% автоморфизмами. Удобно в виде $%a^b$% обозначать результат действия на $%a$% автоморфизмом, задаваемым $%bin A$%. Тогда вся информация о полупрямом произведении содержится в следующей простой формуле: $%b^{-1}ab=a^b$%.
Вместо пары $%(b,a)$% удобно также писать $%ba$% (от одного вида обозначений к другому легко перейти). Пусть $%(beta,alpha)=(b,a)^{-1}$%. Тогда $%(b,a)(beta,alpha)=(1,1)$%, то есть $%babetaalpha=1$%. Это значит, что $%bbeta a^{beta}alpha=1$%, откуда $%beta=b^{-1}$% и $%alpha=(a^{beta})^{-1}=(a^{b^{-1}})^{-1}$%, что удобно записать как $%a^{-b^{-1}}$%. Таким образом, $%(b,a)^{-1}=(b^{-1},a^{-b^{-1}})$%.
Словесно, первый элемент должен быть равен обратному для первого элемента, а второй есть действие обратного автоморфизма на обратном элементе.
Калькулятор для вычисления обратного элемента по модулю ниже, теория под ним.
Обратный элемент в кольце по модулю
Обратным к числу a по модулю m называется такое число b, что:
,
Обратный элемент обозначают как .
Для нуля обратного элемента не существует никогда, для остальных же элементов обратный элемент может как существовать, так и нет.
Утверждается, что обратный элемент существует только для тех элементов a, которые взаимно просты с модулем m.
Для нахождения обратного элемента по модулю можно использовать Расширенный алгоритм Евклида.
Для того, чтобы показать это, рассмотрим следующее уравнение:
Это линейное диофантово уравнение с двумя переменными, см. Линейные диофантовы уравнения с двумя переменными. Посколько единица может делиться только на единицу, то уравнение имеет решение только если .
Решение можно найти с помощью расширенного алгоритма Евклида. При этом, если мы возьмём от обеих частей уравнения остаток по модулю m, то получим:
Таким образом, найденное x и будет являться обратным к a.
Сайт переезжает. Большинство статей уже перенесено на новую версию.
Скоро добавим автоматические переходы, но пока обновленную версию этой статьи можно найти там.
Обратный элемент по модулю
Часто в задачах требуется посчитать что-то по простому модулю (чаще всего (10^9 + 7)). Это делают для того, чтобы участникам не приходилось использовать длинную арифметику, и они могли сосредоточиться на самой задаче.
Обычные арифметические операции выполняются не сильно сложнее — просто нужно брать модули и заботиться о переполнении. Например:
c = (a + b) % mod;
c = (mod + a - b) % mod;
c = a * b % mod;Но вот с делением возникают проблемы — мы не можем просто взять и поделить. Пример: (frac{8}{2} = 4), но (frac{8 % 5 = 3}{2 % 5 = 2} neq 4).
Нужно найти некоторый элемент, который будет себя вести как (frac{1}{a} = a^{-1}), и вместо «деления» домножать на него. Назовем такой элемент обратным.
Способ 1: бинарное возведение в степень
Если модуль (p) простой, то решением будет (a^{-1} equiv a^{p-2}). Это следует из малой теоремы Ферма:
Теорема. (a^p equiv a pmod p) для всех (a), не делящихся на (p).
Доказательство. (для понимания несущественно, можно пропустить)
[
begin{aligned}
a^p &= (underbrace{1+1+ldots+1+1}_text{$a$ раз})^p
\ &= sum_{x_1+x_2+ldots+x_a = p} P(x_1, x_2, ldots, x_a) & text{(раскладываем по определению)}
\ &= sum_{x_1+x_2+ldots+x_a = p} frac{p!}{x_1! x_2! ldots x_a!} & text{(какие слагаемые не делятся на $p$?)}
\ &equiv P(p, 0, ldots, 0) + ldots + P(0, 0, ldots, p) & text{(все остальные не убьют $p$ в знаменателе)}
\ &= a
end{aligned}
]
Здесь (P(x_1, x_2, ldots, x_n) = frac{k}{prod (x_i!)}) это мультиномиальный коеффициент — количество раз, которое элемент (a_1^{x_1} a_2^{x_2} ldots a_n^{x_n}) появится при раскрытии скобки ((a_1 + a_2 + ldots + a_n)^k).
Теперь два раза «поделим» наш результат на (a).
[ a^p equiv a implies a^{p-1} equiv 1 implies a^{p-2} equiv a^{-1} ]
Получается, что (a^{p-2}) ведет себя как (a^{-1}), что нам по сути и нужно. Посчитать (a^{p-2}) можно за (O(log p)) бинарным возведением в степень.
Приведем код, который позволяет считает (C_n^k).
int t[maxn]; // факториалы, можно предподситать простым циклом
// бинарное возведение в степень
int bp (int a, int n) {
int res = 1;
while (n) {
if (n & 1) res = res * a % mod;
a = a * a % mod;
n >>= 1;
}
return res;
}
// находит обратный элемент как a^(p-2)
int inv (int x) {
return bp(x, mod-2);
}
int c (int n, int k) {
return t[n] * inv(t[k]) % mod * inv(t[n-k]) % mod;
}Способ 2: диофантово уравнение
Диофантовыми уравнениями называют такие штуки:
[ ax + by = 1 ]
Требуется решить их в целых числах, то есть (a) и (b) известны, и нужно найти такие целые (возможно, отрицательные) (x) и (y), чтобы равенство выполнялось. Решают такие вещи расширенным алгоритмом Евклида. TODO: описать, как он работает.
Подставим в качестве (a) и (b) соответственно (a) и (m)
[ ax + my = 1 ]
Одним из решений уравнения и будет (a^{-1}), потому что если взять уравнение по модулю (m), то получим
[ ax + by = 1 iff ax equiv 1 iff x equiv a^{-1} pmod m ]
Преимущества этого метода над возведением в степень:
- Если обратное существует, то оно найдется даже если модуль не простой. Способ с бинарным возведением тоже можно заставить работать с произвольным модулем, но это будет намного труднее.
- Алгоритм проще выполнять руками.
Сам автор почти всегда использует возведение в степень.
Почему (10^9+7)?
- Это выражение довольно легко вбивать (
1e9+7). - Простое число.
- Достаточно большое.
intне переполняется при сложении.long longне переполняется при умножении.
Кстати, (10^9 + 9) обладает теми же свойствами. Иногда используют и его.
Предподсчёт обратных факториалов за линейное время
Пусть нам нужно зачем-то посчитать все те же (C_n^k), но для больших (n) и (k), поэтому асимптотика (O(n log m)) нас не устроит. Оказывается, мы можем сразу предподсчитать все обратные ко всем факториалам.
Если у нас уже написан inv, то нам не жалко потратить (O(log m)) операций, посчитав (m!^{-1}).
После этого мы будем считать ((m-1)!^{-1}) как (m!^{-1} m = frac{1}{1 cdot 2 cdot ldots cdot (m-1)}).
int f[maxn];
f[0] = 1;
for (int i = 1; i < maxn; i++)
f[i] = i*f[i-1] % mod;
int r[maxn];
r[maxn-1] = inv(f[maxn-1])
for (int i = maxn-1; i >= 1; i--)
r[i-1] = r[i]*i % mod;TODO: техника с сайта емакса.
Обратный по модулю
❓Инструкция
Калькулятор онлайн для вычисления обратного элемента по модулю в кольце. Алгоритм поддерживает работу с большими числами с некоторыми ограничениями.
Использование:
Заполняются два поля — число 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.
Обра́тный элеме́нт — одно из понятий абстрактной алгебры.
Содержание
- 1 Определения
- 2 Замечания
- 3 Свойства
- 4 Примеры
- 5 См. также
Определения
- Пусть — множество с определённой на нём бинарной операцией . Пусть — произвольный элемент множества . Если справедливо равенство
где, а — нейтральный элемент относительно операции , то называется обра́тным спра́ва к . - Аналогичным образом, если выполнено
то называется обра́тным сле́ва к . - Элемент , являющийся обратным к и справа, и слева, то есть такой, что
называется просто обратным к и обозначается .
Замечания
- Приведённое выше определение дано в мультипликативной нотации. Если используется аддитивная нотация , то обратный элемент называется противополо́жным и обозначается .
- Вообще говоря, один и тот же элемент может иметь несколько обратных слева элементов и несколько обратных справа элементов, и последние не обязаны пересекаться.
Свойства
- Пусть операция ассоциативна. Тогда если для элемента определены обратный слева и обратный справа элементы, то они равны и единственны.
Примеры
| Множество | Бинарная операция | Обратный элемент |
|---|---|---|
| Вещественные числа |  (сложение) |
|
| Вещественные числа не равные нулю |  (умножение) |
|
Функции вида  |
 (композиция функций) |
 (обратная функция)
|
См. также
- Группа.
bg:Обратен елемент
cs:Inverzní prvek
he:איבר הופכי
nl:Inverse element
pl:Element odwrotny
sk:Inverzný prvok