Как найти обратное число mod

c = (a + b) % mod;
c = (mod + a - b) % mod;
c = a * b % mod;

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;
}

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;

1. Основные способы нахождения обратных величин

Существуют
три основных способа нахождения обратных
величин

а ^–1 ≡ х (mod
n).

1. Проверить поочередно
   значения 1, 2, … , n – 1,
   пока не будет найден а ^{– 1} 
   1 (mod n),
   такой, что а • а ^–1 (mod
   n) 
   1.

1. Если известна
   функция Эйлера (n),
   то можно вычислить

а ^–1 (mod
n) 
а ^{(n)
– 1} (mod n),

используя алгоритм
быстрого возведения в степень.

1. Если функция
   Эйлера (n)
   не известна, можно использовать
   расширенный алгоритм Евклида.

Примеры.

1. Поочередная
   проверка значений 1, 2, … , n
   – 1, пока не будет найден х = а ^{– 1}
   (mod n), такой,
   что а • х 
   1 (mod n).

Пусть
n = 7, a = 5.
Найти х = а ^{– 1} (mod
n).

а • х 
1 (mod n) или
5 • х 
1

n – 1 = 7
– 1 = 6.

Получаем
х = 5 ^{– 1} (mod 7) = 3.

Результаты
проверки приведены в таблице 1.4.1.

Таблица
1.4.1 – Нахождение обратной величины
первым способом

х	5 • х	5 • х (mod 7)
1 2 3 4 5 6	5 10 15 20 25 30	5 3 1 6 4 2

1. Нахождение а ^–1
   (mod n),
   если известна функция Эйлера (n).

Пусть
n = 7, a = 5.
Найти х = а ^{– 1} (mod
n) = 5 ^–1 (mod
7).

Модуль
n = 7 – простое число.
Поэтому функция Эйлера

(n) =
(7) =
n – 1 = 6.

Обратная
величина от5 по mod 7:

а ^–1
(mod n) =
а ^{(n)
– 1} (mod n) = 5 ^{6
– 1} mod 7 = 5 ⁵
mod 7 =

= (5 ²
mod 7) (5 ³
mod 7) mod 7 = (25
mod 7) (125
mod 7) mod 7 =

= (4 • 6) mod
7 = 24 mod 7 = 3.

Итак,
х = 5 ^–1 (mod 7) = 3.

3. Нахождение обратной величины а ^–1
(mod n) с
помощью расширенного алгоритма Евклида.

Алгоритм
Евклида можно обобщить способом, который
имеет большое практическое значение.
При этом способе во время вычисления
НОД (а, b) можно попутно
вычислить такие целые числа u₁
и u₂, что

а • u₁
+ b • u₂
= НОД (а, b).

Это
обобщение (расширение) алгоритма Евклида
удобно описать, используя векторные
обозначения.

1. Расширенный алгоритм Евклида

При
заданных неотрицательных целых числах
а и b
этот алгоритм определяет вектор (u₁,
u₂,
u₃),
такой, что

а • u₁
+ b • u₂
= u₃ = НОД (а, b).

В
процессе вычисления используются
вспомогательные векторы (v₁,
v₂, v₃),
(t₁, t₂,
t₃). Действия с
векторами производятся таким образом,
что в течение всего процесса вычисления
выполняются соотношения

а • t₁ + b
• t₂ = t₃,

а • u₁
+ b • u₂
= u₃,

а • v₁
+ b • v₂
= v₃.

Для
вычисления обратной величины а ^–1
(mod
n)
используется частный режим работы
расширенного алгоритма Евклида, при
котором:

b
= n,
НОД (а, n)
= 1, и этот алгоритм определяет вектор
(u₁,
u₂,
u₃),
такой, что

u₃ =
1, а • u₁ + n
• u₂ = НОД (а, n)
= 1,

(а
• u₁ +
n • u₂)
mod n 
а • u₁
(mod n) 
1,

а ^–1
(mod n) 
u₁ (mod
n).

Шаги
алгоритма:

1. Начальная установка.

Установить
(u₁, u₂,
u₃) : = (0, 1, n),

(v₁,
v₂,
v₃) :
= (1, 0, a).

1. u₃
   = 1 ?. Если u₃ = 1,
   то алгоритм останавливается.

2. Разделить, вычесть.

Установить
q : = [u₃
/ v₃].

Затем
установить

(t₁,
t₂,
t₃) :
= (u₁,
u₂,
u₃) –
(v₁,
v₂,
v₃) •
q,

(u₁,
u₂,
u₃) :
= (v₁,
v₂,
v₃),

(v₁,
v₂,
v₃) :
= (t₁,
t₂,
t₃).

Возвратиться
к шагу 2.

Пример.
Даны модуль n = 23 и число
а = 5.

Найти обратное число а ^–1
(mod 23), т.е. х = 5 ^–1
(mod 23).

Используя
расширенный алгоритм Евклида, выполним
вычисления, записывая результаты
отдельных шагов в таблицу 1.5.1.

Таблица
1.5.1 – Шаги выполнения алгоритма Евклида

q	u1	u2	u3	v1	v2	v3
— 4 1 1 —	0 1 — 4 5 -9	1 0 1 — 1 2	n = 23 5 3 2 1	1 — 4 5 — 9	0 1 — 1 2	a = 5 3 2 1

При
u₃
= 1, u₁
= — 9, u₂
= 2.

(а
• u₁ +
n • u₂)
mod n = (5 • (- 9) +
23 • 2) mod 23 = 5 • (- 9)
mod 23 
1,

а ^–1
(mod n) = 5 ^–1
(mod 23) = (- 9) (mod 23) = (- 9 +
23) (mod 23) = 14.

Таким
образом, х = 5 ^–1 (mod
23) 
14 (mod 23) = 14.

Для
решения более сложных сравнений

а • х 
b (mod n),
т.е. b 
1, x = ?

используется следующий
прием. Сначала решают сравнение

а • y

1 (mod n),

т.е. определяют
y = a
^–1 (mod n),

а затем находят

x = a
^–1 • b (mod
n) = y • b
(mod n).

Пример.
Найти х для сравнения 5 • х
 9
(mod 23).

Сначала
решаем сравнение 5 • y

1 (mod 23).

Получаем
y = 5 ^–1 (mod
23) = 14. Затем находим

x
= 5 ^–1 • 9 (mod 23) = 14 •
9 (mod 23) = 126 (mod
23) 
11 (mod 23).

x = 11.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

Вычисление обратного элемента в кольце по модулю с использованием расширенного алгоритма Евклида (max_algo)

def gcdex(a, b):
    if a == 0 :
        return b,0,1
    gcd,x,y = gcdex(b%a, a)
    return gcd, y - (b//a) * x, x

def invmod(a, m):
    g, x, y = gcdex (a, m)
    return None if g > 1 else (x % m + m) % m

print(invmod(4,11)) # result 3    (4 * 3) % 11 = 1