← Назад к математике

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

Нахождение обратного элемента с помощью расширенного алгоритма Евклида

🐍 Python
def mod_inverse(a, m):
    m0 = m
    y = 0
    x = 1
    if m == 1:
        return 0
    while a > 1:
        q = a // m
        t = m
        m = a % m
        a = t
        t = y
        y = x - q * y
        x = t
    if x < 0:
        x += m0
    return x

a, m = map(int, input().split())

# Проверка НОД
g = mod_inverse(a, m)
if g == 0:
    print(-1)
else:
    print(g)
⚙️ C++
#include <bits/stdc++.h>
using namespace std;

long long mod_inverse(long long a, long long m) {
    long long m0 = m;
    long long y = 0, x = 1;
    if (m == 1) return 0;
    while (a > 1) {
        long long q = a / m;
        long long t = m;
        m = a % m;
        a = t;
        t = y;
        y = x - q * y;
        x = t;
    }
    if (x < 0) x += m0;
    return x;
}

int main() {
    long long a, m;
    cin >> a >> m;
    
    long long inv = mod_inverse(a, m);
    if (inv == 0) {
        cout << -1 << endl;
    } else {
        cout << inv << endl;
    }
    return 0;
}

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

Уравнение a·x + m·y = 1 имеет решение тогда и только тогда, когда НОД(a, m) = 1. В этом случае x является обратным к a по модулю m.

a·x ≡ 1 (mod m) → a·x + m·y = 1

Алгоритм

Расширенный алгоритм Евклида находит x и y, удовлетворяющие этому уравнению. Затем x приводится к положительному значению.

Преимущества

Временная сложность: O(log min(a, m))

Формат ввода и вывода

Ввод: a m — число и модуль

Вывод: обратный элемент или -1, если НОД(a, m) ≠ 1

Пример:

3 7

Вывод: 5

Пример (не взаимно простые):

2 4

НОД(2,4) = 2 ≠ 1 → обратного не существует

Вывод: -1

Попробовать онлайн

Результат появится здесь...