Как найти обратный элемент группы

Пусть даны группы $%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}})$%.

Словесно, первый элемент должен быть равен обратному для первого элемента, а второй есть действие обратного автоморфизма на обратном элементе.

Источник

Калькулятор для вычисления обратного элемента по модулю ниже, теория под ним.

PLANETCALC, Обратный элемент в кольце по модулю

Обратный элемент в кольце по модулю

Обратным к числу a по модулю m называется такое число b, что:
ab equiv 1 pmod m,
Обратный элемент обозначают как a^{-1}.

Для нуля обратного элемента не существует никогда, для остальных же элементов обратный элемент может как существовать, так и нет.
Утверждается, что обратный элемент существует только для тех элементов a, которые взаимно просты с модулем m.

Для нахождения обратного элемента по модулю можно использовать Расширенный алгоритм Евклида.

Для того, чтобы показать это, рассмотрим следующее уравнение:

ax + my = 1

Это линейное диофантово уравнение с двумя переменными, см. Линейные диофантовы уравнения с двумя переменными. Посколько единица может делиться только на единицу, то уравнение имеет решение только если {rm gcd}(a,m)=1.
Решение можно найти с помощью расширенного алгоритма Евклида. При этом, если мы возьмём от обеих частей уравнения остаток по модулю m, то получим:

ax = 1 pmod 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)?

  1. Это выражение довольно легко вбивать (1e9+7).
  2. Простое число.
  3. Достаточно большое.
  4. int не переполняется при сложении.
  5. 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 См. также

Определения

  • Пусть {displaystyle (M,cdot )} — множество {displaystyle M} с определённой на нём бинарной операцией {displaystyle cdot }. Пусть {displaystyle xin M} — произвольный элемент множества {displaystyle M}. Если справедливо равенство
        {displaystyle xcdot y=e,}
    где {displaystyle yin M}, а {displaystyle ein M} — нейтральный элемент относительно операции {displaystyle cdot }, то {displaystyle y} называется обра́тным спра́ва к {displaystyle x}.
  • Аналогичным образом, если выполнено
        {displaystyle ycdot x=e,}
    то {displaystyle y} называется обра́тным сле́ва к {displaystyle x}.
  • Элемент {displaystyle yin M}, являющийся обратным к {displaystyle x} и справа, и слева, то есть такой, что
        {displaystyle xcdot y=ycdot x=e,}
    называется просто обратным к {displaystyle x} и обозначается {displaystyle x^{-1}}.

Замечания

  • Приведённое выше определение дано в мультипликативной нотации. Если используется аддитивная нотация {displaystyle (M,+)}, то обратный элемент называется противополо́жным и обозначается {displaystyle -x}.
  • Вообще говоря, один и тот же элемент {displaystyle xin M} может иметь несколько обратных слева элементов и несколько обратных справа элементов, и последние не обязаны пересекаться.

Свойства

  • Пусть операция {displaystyle cdot } ассоциативна. Тогда если для элемента {displaystyle xin M} определены обратный слева и обратный справа элементы, то они равны и единственны.

Примеры

Множество Бинарная операция Обратный элемент
Вещественные числа {displaystyle +} (сложение) {displaystyle -x}
Вещественные числа не равные нулю {displaystyle cdot } (умножение) {displaystyle 1/x}
Функции вида {displaystyle f:Mto M} {displaystyle circ } (композиция функций) {displaystyle f^{-1}} (обратная функция)

См. также

  • Группа.

bg:Обратен елемент
cs:Inverzní prvek
he:איבר הופכי
nl:Inverse element
pl:Element odwrotny
sk:Inverzný prvok

Источник

Понравилась статья? Поделить с друзьями:
  • Как найти чнп в задаче
  • Как правильно найти свою девушку
  • Как найти своих родственников в архангельске
  • Правило по математике как найти неизвестный множитель
  • Как найти деревню в майнкрафт на компьютер