Modular Inverse

Modular Inverse

모듈러 역원은 모듈로 연산에서 곱셈의 역원을 의미합니다. 덧셈, 곱셈에서의 모듈러 연산은 다음과 같이 단순하게 처리할 수 있습니다.

나머지 연산을 %로 표현하는 것은 수학적으로 엄일한 표현은 아니지만, 편의를 위해 사용하겠습니다.

여기서 하고 싶은 것은 나눗셈에서 모듈러 연산을 처리하는 것입니다. 나눗셈은 위의 방식처럼 간단히 처리할 수 없습니다. 그래서 모듈러 역원을 사용합니다.

모듈러 연산의 항등원

역원을 정의하기 위해서는 항등원을 먼저 정의해야 합니다. 덧셈에서의 항등원은 0이고 곱셈에서의 항등원은 1입니다. 모듈러 연산은 덧셈과 곱셈의 항등원이 다릅니다. 항등원은 어떤 수 \( a \)가 있을 때 연산 결과를 그대로 \( a \)가 나오게 하는 수입니다. \( a \,\%\, b = c \)인 \( a \)에 대해 모듈러 합의 항등원은 다음 식을 만족합니다.

이를 항상 만족하는 수 \( e \)는 0입니다. 따라서 모듈러 합에서의 항등원은 0입니다. 마찬가지로 모듈러 곱에서는 다음 식을 만족합니다.

이를 항상 만족하는 수 \( e \)는 1입니다. 따라서 모듈러 곱에서의 항등원은 1입니다. 어떤 수의 역원은 그 수와 연산했을 때 항등원이 되는 수입니다. 모듈러 합에서는 연산 결과가 0이 되게 하는 수가 역원입니다. 즉, \( -a \)가 \( a \)의 모듈러 합의 역원입니다. 모듈러 곱에서는 다음과 같이 표현할 수 있습니다.

이때의 \( x \)가 \( a \)의 모듈러 곱의 역원 \( a^{-1} \)입니다. 이 \( x \)를 찾을 수 있다면 나눗셈을 역원의 곱으로 표현할 수 있게 됩니다. 위 식을 살짝 변형하면 \( ax = Ny + 1 \)으로 표현할 수 있습니다. 이 식을 정리하면,

으로 표현할 수 있습니다. \( y \)는 임의의 상수이기 때문에 편의상 부호를 바꾸어 썼습니다. 이 식은 베주 항등식(Bézout's identity)과 동일한 형태입니다.

Bézout's identity

두 정수 \( a, b \)가 있을 때

를 만족하는 정수 \( x, y \)가 항상 존재한다는 것이 베주 항등식입니다. 위 식의 형태와 비슷합니다. 위 식에서 우변이 1이기 때문에 \( \gcd(a, N) = 1 \)이 되어야 합니다. 즉, \( a \)와 \( N \)이 서로소여야 모듈러 역원이 존재합니다. PS에서 \( N \)이 보통 1,000,000,007로 주어집니다. 이 수가 자주 사용되는 것은 이 수가 소수이기 때문입니다. 즉, 모든 \( a \)에 대해 \( \gcd(a, N) = 1 \)이 됩니다. 이 외에도 998,244,353 같은 소수도 자주 사용됩니다.

이제 이 식을 만족하는 정수해 \( (x, y) \)를 찾을 수 있다면 \( x \)가 \( a \)의 모듈러 곱의 역원이 됩니다. 이 식의 해를 구하는 방법은 확장 유클리드 알고리즘이 있습니다.

Extended Euclidean Algorithm

확장 유클리드 알고리즘은 유클리드 알고리즘을 확장하여 베주 항등식의 해를 구하는 알고리즘입니다. gcd를 구하면서 동시에 \( x, y \)도 구할 수 있습니다. 두 정수 \( a, b \)에 대해 \( a = qb + r \)로 표현할 수 있습니다. 이때 유클리드 호제법에 의해 다음이 성립합니다.

즉, \( \gcd = ax + by \)를 \( \gcd = bx' + ry' \)으로 변형할 수 있습니다. 이때 \( r = a - qb \) 이므로 이를 대입하면

가 됩니다. 따라서 원래 문제 \( (a, b) \)에 대한 베주 계수는

임을 알 수 있습니다. 이 과정을 재귀적으로 반복해 \( x, y \)를 구할 수 있게 됩니다. 유클리드 호제법의 종료 조건은 \( r = 0 \)이 되는 경우입니다. 식으로 표현하면 \( \gcd(a, 0) = a \)입니다. 이를 베주 항등식의 형태로 표현하면 \( ax + 0y = a \)이므로 이 경우의 계수는 \( x = 1 \)이고 \( y = 0 \)이 됩니다. 이후 재귀 호출이 반환되면서 위의 갱신식에 따라 각 단계의 \( x, y \)가 결정됩니다.

예를 들어, \( a = 30, b = 18 \)인 경우를 생각해봅시다.

이 과정을 거꾸로 올라가면서 \( x, y \)를 구합니다. \( (12, 6) \to (18, 12) \to (30, 18) \)의 순서로 올라갑니다. 먼저 종료 조건에서

이므로 \( x = 0, y = 1 \)입니다. 다음 단계인 \( (18, 12) \)에서는 \( 6 = 18 \,\%\, 12 = 18 - 1\cdot 12 \)이므로 이를 대입하면

이 되어 \( x = 1 \), \( y = -1 \)입니다. 마지막으로 \( (30, 18) \) 단계에서는 \( 12 = 30 \,\%\, 18 = 30 - 1\cdot 18 \)이므로 이를 대입하면

가 됩니다. 따라서 \( x = -1, y = 2 \)이며,

이 성립합니다. 따라서 \( (-1, 2) \)가 \( 30, 18 \)의 베주 항등식의 해입니다. 확장 유클리드 알고리즘을 코드로 구현하면 다음과 같습니다.

pair<int, pair<int, int>> eea(int a, int b) {
    if (b == 0) return { a, {1, 0} };
    
    auto [g, xy] = eea(b, a % b);
    auto [x, y] = xy;
    return { g, { y, x - (a / b) * y  }};
}

이제 확장 유클리드 알고리즘을 사용하여 모듈러 역원을 구할 수 있게 되었습니다. 이때, 확장 유클리드의 결과가 음수일 수 있기 때문에 양수로 변환해 사용합니다.

int mod_inv(int a, int mod) {
    auto res = eea(a, mod);
    if (res.first != 1) return -1;
    return (res.second.first % mod + mod) % mod;
}

BOJ 14565번: 역원(Inverse) 구하기를 풀어 보겠습니다. 이 문제는 \( N \)에 대한 \( A \)의 모듈러 합과 곱의 역원을 구하는 문제입니다. 모듈러 합의 역원 \( -A \)입니다. 다만, 요구하는 답이 0부터 \( n - 1 \) 사이의 정수이므로 \( N - A \)가 됩니다. 모듈러 곱의 역원은 위의 mod_inv 함수에 통과시키면 됩니다.

#include <bits/stdc++.h>

using namespace std;
void fio() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); }

typedef long long ll;

pair<ll, pair<ll, ll>> eea(ll a, ll b) {
    if (b == 0) return { a, {1, 0} };

    auto [g, xy] = eea(b, a % b);
    auto [x, y] = xy;
    return { g, { y, x - (a / b) * y }};
}

ll mod_inv(ll a, ll mod) {
    auto res = eea(a, mod);
    if (res.first != 1) return -1;
    return (res.second.first % mod + mod) % mod;
}

int main() {
    fio();

    ll n, a; cin >> n >> a;
    cout << n - a << ' ' << mod_inv(a, n);
}