Как найти обратную величину по модулю - AvtoShod.ru

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

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

(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 ³ имеет 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 = 18 элементов.

Число
элементов в приведенном наборе вычетов
характеризует функция Эйлера
(n).

Таблица
1.3.1 – Функция Эйлера (n)

Модуль n

Функция (n)

n ²

. . .

n^r

n – 1

n •
(n – 1)

. . .

n ^{r – 1} •
(n – 1)

p • q
(p, q —
простые)

. . .

_i^eⁱ
(p _i— простые)

(p – 1)
• (q – 1)

. . .

_i^eⁱ
(p _i–
1)

Иначе
говоря, функция (n)
– это количество положительных целых,
меньших n,
которые взаимно просты с n.

Малая
теорема Ферма:
если n
– простое и НОД (а, n)
= 1, то

а
ⁿ^{– 1} 
1 (mod
n).

Согласно
обобщению Эйлером
малой теоремы Ферма имеем: если НОД
(а, n)
= 1, то

а
^⁽ⁿ⁾ 
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. [Инициализация] (a₀, a₁) := (a, m); (x₀, x₁) := (1, 0); (y₀; y₁) := (0, 1).

2. [Основной цикл] Пока a₁ ≠ 0 выполнять {q = QUO(a₀, a₁);
(a₀, a₁) := (a₁, a_{0 —}a₁q); (x₀, x₁) := (x₁, x_{0 —}x₁q); (y₀, y₁) := (y₁, y_{0 —}y₁q);

QUO(a₀, a₁) — целая часть от деления a₀ на a₁

3. [Выход] Вернуть (d, x, y) = (a₀, x₀, y₀)

Битовая сложность расширенного алгоритма Евклида равна O((log₂(n))²) , где 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) = (a₀, x₀, y₀)

(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^{-1}$ .

Для нуля обратного элемента не существует никогда, для остальных же элементов обратный элемент может как существовать, так и нет.
Утверждается, что обратный элемент существует только для тех элементов 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.

Источник

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

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

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

Пример: A=3, C=7

Шаг 1. Вычисляем A * B mod C для значений B от 0 до C-1

Шаг 2. Обратным значением для A mod C является такое B, при котором A * B mod C = 1

Пример: A=2, C=6

Шаг 1. Вычисляем A * B mod C для всех B от 0 до C-1**

Шаг 2. Обратным значением для A mod C является такое B, при котором A * B mod C = 1

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

Вычисление обратных величин

Обратный по модулю

<img decoding="async" onError="javascript: wp_broken_images = window.wp_broken_images || function(){}; wp_broken_images(this);" src="https://ilovecalc.com/wp-content/uploads/desc_emoji/f09f938dcdef.png" alt="📌" /> Что значит по модулю?

<img decoding="async" onError="javascript: wp_broken_images = window.wp_broken_images || function(){}; wp_broken_images(this);" src="https://ilovecalc.com/wp-content/uploads/desc_emoji/f09f938dcdef.png" alt="📌" /> Что такое обратное?

<img decoding="async" onError="javascript: wp_broken_images = window.wp_broken_images || function(){}; wp_broken_images(this);" src="https://ilovecalc.com/wp-content/uploads/desc_emoji/f09f938dcdef.png" alt="📌" /> Что такое обратное по модулю?

<img decoding="async" onError="javascript: wp_broken_images = window.wp_broken_images || function(){}; wp_broken_images(this);" src="https://ilovecalc.com/wp-content/uploads/desc_emoji/f09f938dcdef.png" alt="📌" /> Как найти модульный обратный

<img decoding="async" onError="javascript: wp_broken_images = window.wp_broken_images || function(){}; wp_broken_images(this);" src="https://ilovecalc.com/wp-content/uploads/desc_emoji/f09f938dcdef.png" alt="📌" /> Расширенный алгоритм Евклида

<img decoding="async" onError="javascript: wp_broken_images = window.wp_broken_images || function(){}; wp_broken_images(this);" src="https://ilovecalc.com/wp-content/uploads/desc_emoji/f09f938dcdef.png" alt="📌" /> Алгоритм:

<img decoding="async" onError="javascript: wp_broken_images = window.wp_broken_images || function(){}; wp_broken_images(this);" src="https://ilovecalc.com/wp-content/uploads/desc_emoji/f09f938dexample.png" alt="📍" /> Пример для наивного метода.

<img decoding="async" onError="javascript: wp_broken_images = window.wp_broken_images || function(){}; wp_broken_images(this);" src="https://ilovecalc.com/wp-content/uploads/desc_emoji/f09f938dexample.png" alt="📍" /> Пример на расширенный алгоритм Евклида.

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

Не пропустите также:

**Шаг 2. Обратным значением для A mod C является такое B, при котором A * B mod C = 1**

**Шаг 2. Обратным значением для A mod C является такое B, при котором A * B mod C = 1**

Что значит по модулю?

Что такое обратное?

Что такое обратное по модулю?

Как найти модульный обратный

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

Алгоритм:

Пример для наивного метода.

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