모듈러 역원 (Modular Multiplicative Inverse)

정의

정수 a 의 모듈러 역원 (modular multiplicative inverse) 은 a·x ≡ 1 (mod m) 을 만족하는 정수 x. 기호로 a⁻¹ (mod m) 또는 inv(a, m).

존재 조건: gcd(a, m) = 1 일 때만 유일한 역원 존재 (mod m 에서).

주요 계산법:

1. 확장 유클리드 호제법 (일반 mod, O(log m))
2. Fermat 의 소정리 (m 이 소수, O(log m) 거듭제곱)
3. Euler 정리 (gcd(a, m)=1, O(log m) 거듭제곱 + φ(m) 전처리)

문제 상황과 동기

나눗셈을 mod 에서 할 수 없을 때:

(a / b) mod m  (X, 정의되지 않음)
→ a · b⁻¹ mod m  (O, b 의 역원으로 곱셈 변환)

조합론 mod 계산 (nCr mod p):

• nCr = n! / (r! · (n-r)!) → n! · inv(r!) · inv((n-r)!) mod p

분수 계수 DP, 확률 DP 에서 mod 1e9+7 로 정규화할 때 필수.

RSA 암호: 공개키 e 의 역원 d 를 φ(n) 에서 구함.

시각화

핵심 아이디어

1. 확장 유클리드: ax + my = gcd(a, m) 의 정수해 (x, y) 구하기.

   • gcd(a, m) = 1 이면 ax + my = 1 → ax ≡ 1 (mod m) → x 가 역원.
   • x 를 0 ≤ x < m 범위로 정규화: (x % m + m) % m.

2. Fermat 의 소정리 (m = p 소수):

   • aᵖ⁻¹ ≡ 1 (mod p) (gcd(a, p)=1).
   • a · aᵖ⁻² ≡ 1 (mod p) → inv(a, p) = aᵖ⁻² mod p.
   • 분할 정복 거듭제곱 O(log p).

3. Euler 정리 (일반 m):

   • a^φ(m) ≡ 1 (mod m) (gcd(a, m)=1).
   • inv(a, m) = a^(φ(m)-1) mod m.

invariant: a · inv(a, m) ≡ 1 (mod m) 항상 성립.

알고리즘

확장 유클리드 방식

inv_exgcd(a, m):
    (g, x, y) = exgcd(a, m)
    if g != 1:
        return None   # 역원 없음
    return (x % m + m) % m

Fermat 의 소정리 (m 소수)

inv_fermat(a, p):
    return pow(a, p - 2, p)   # a^(p-2) mod p

Euler 정리 (일반 m)

inv_euler(a, m):
    phi = euler_phi(m)
    return pow(a, phi - 1, m)

구현

// 모듈러 역원: 확장 유클리드 + Fermat 소정리
#include <bits/stdc++.h>
using namespace std;
​
// 확장 유클리드
tuple<long long, long long, long long> exgcd(long long a, long long b) {
  if (b == 0) return {a, 1, 0};
  auto [g, x1, y1] = exgcd(b, a % b);
  return {g, y1, x1 - (a / b) * y1};
}
​
// 역원 (일반 mod, 확장 유클리드)
long long inv_exgcd(long long a, long long m) {
  auto [g, x, y] = exgcd(a, m);
  if (g != 1) return -1;  // 역원 없음
  return (x % m + m) % m;
}
​
// 역원 (소수 mod, Fermat)
long long pow_mod(long long a, long long n, long long m) {
  long long r = 1;
  a %= m;
  while (n > 0) {
      if (n & 1) r = r * a % m;
      a = a * a % m;
      n >>= 1;
  }
  return r;
}
long long inv_fermat(long long a, long long p) {
  return pow_mod(a, p - 2, p);
}
​
int main() {
  long long a, m;
  cin >> a >> m;
  
  long long inv1 = inv_exgcd(a, m);
  cout << "exgcd: " << inv1 << "\n";
  
  // m 이 소수라 가정
  long long inv2 = inv_fermat(a, m);
  cout << "fermat: " << inv2 << "\n";
  
  // 검증
  if (inv1 != -1)
      cout << "verify: " << (a * inv1) % m << " == 1\n";
  return 0;
}

# 모듈러 역원: 확장 유클리드 + pow(a, -1, m) (Python 3.8+)
def exgcd(a, b):
  if b == 0:
      return (a, 1, 0)
  g, x1, y1 = exgcd(b, a % b)
  return (g, y1, x1 - (a // b) * y1)
​
def inv_exgcd(a, m):
  g, x, y = exgcd(a, m)
  if g != 1:
      return None
  return (x % m + m) % m
​
def inv_fermat(a, p):
  return pow(a, p - 2, p)
​
a, m = map(int, input().split())
​
inv1 = inv_exgcd(a, m)
print(f"exgcd: {inv1}")
​
# Python 3.8+ 내장 (확장 유클리드)
inv_builtin = pow(a, -1, m)
print(f"builtin: {inv_builtin}")
​
# m 이 소수라 가정
inv2 = inv_fermat(a, m)
print(f"fermat: {inv2}")
​
if inv1:
  print(f"verify: {(a * inv1) % m} == 1")

// 확장 유클리드 + 분할 정복 거듭제곱
import java.util.*;
public class Main {
  static long[] exgcd(long a, long b) {
      if (b == 0) return new long[]{a, 1, 0};
      long[] r = exgcd(b, a % b);
      return new long[]{r[0], r[2], r[1] - (a / b) * r[2]};
  }
  static long invExgcd(long a, long m) {
      long[] r = exgcd(a, m);
      if (r[0] != 1) return -1;
      return (r[1] % m + m) % m;
  }
  static long powMod(long a, long n, long m) {
      long res = 1;
      a %= m;
      while (n > 0) {
          if ((n & 1) == 1) res = res * a % m;
          a = a * a % m;
          n >>= 1;
      }
      return res;
  }
  static long invFermat(long a, long p) {
      return powMod(a, p - 2, p);
  }
  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      long a = sc.nextLong(), m = sc.nextLong();
      long inv1 = invExgcd(a, m);
      System.out.println("exgcd: " + inv1);
      long inv2 = invFermat(a, m);
      System.out.println("fermat: " + inv2);
      if (inv1 != -1)
          System.out.println("verify: " + (a * inv1 % m) + " == 1");
  }
}

5 1000000007

exgcd: 400000003
fermat: 400000003
verify: 1 == 1

7 26

exgcd: 15
fermat: 15
verify: 1 == 1

복잡도

PS 에서는 mod 1e9+7 (소수) 이 대부분 → Fermat 가 간단. 일반 mod 는 확장 유클리드.

응용

1. 조합론 mod p (nCr)

// nCr mod p (p 소수)
long long fact[MAXN], inv_fact[MAXN];
void precompute(long long p) {
    fact[0] = 1;
    for (int i = 1; i < MAXN; i++)
        fact[i] = fact[i-1] * i % p;
    inv_fact[MAXN-1] = inv_fermat(fact[MAXN-1], p);
    for (int i = MAXN-2; i >= 0; i--)
        inv_fact[i] = inv_fact[i+1] * (i+1) % p;
}
long long nCr(int n, int r, long long p) {
    if (r < 0 || r > n) return 0;
    return fact[n] * inv_fact[r] % p * inv_fact[n-r] % p;
}

O(N) 전처리 + O(1) 쿼리.

2. 분수 계수 DP

# DP[i] = (분자) / (분모) mod p
MOD = 10**9 + 7
dp = [0] * N
dp[0] = 1
for i in range(N-1):
    # dp[i+1] = dp[i] · 2 / 3
    dp[i+1] = dp[i] * 2 % MOD * pow(3, -1, MOD) % MOD

3. 확률 mod 계산

기댓값 E = Σ p_i · x_i, p_i = a/b 일 때:

• p_i mod m = a · inv(b, m) mod m

함정

1. gcd(a, m) ≠ 1

역원 존재하지 않음. 확인 없이 계산하면 WA 또는 런타임 에러.

if (gcd(a, m) != 1) {
    // 역원 없음 처리
}

2. Fermat 를 비소수 mod 에

pow(a, m-2, m) 을 m 이 합성수일 때 쓰면 틀림. m 소수 여부 체크 필수.

3. 음수 역원

확장 유클리드에서 나온 x 가 음수일 수 있음. (x % m + m) % m 로 정규화.

4. 오버플로우

C++ 에서 a * inv % m 계산 시 중간 값이 long long 넘을 수 있음. (__int128)a * inv % m 또는 곱셈 mod 함수 사용.

5. 0 의 역원

0 은 역원 없음 (gcd(0, m) = m ≠ 1). 예외 처리.

변형

BOJ 연습 문제

참고

• 확장 유클리드 호제법
• Fermat 의 소정리
• 오일러 파이 함수
• 조합론