백준 등 프로그래밍 문제에서 “결과를 10^9+7로 나눈 나머지를 출력하라”는 지시를 자주 본다. 오버플로우를 막기 위함도 있지만, 그 값이 소수여야 하는 이유는 모듈러 역원과 관련되어있다.
곱셈 역원
실수에서 나눗셈은 역수를 곱하는 것과 같다. a / b = a × (1/b). 모듈러 연산에서도 비슷한 개념이 있는데, 이를 모듈러 곱셈 역원(modular multiplicative inverse)이라 한다.
b의 mod p에서의 곱셈 역원 b⁻¹은, b × b⁻¹ ≡ 1 (mod p)를 만족하는 정수다. 이 값이 존재하면 a / b mod p 대신 a × b⁻¹ mod p를 계산할 수 있다.
핵심은, p가 소수일 때 b와 p가 서로소인 모든 b에 대해 곱셈 역원이 항상 존재한다는 것이다 (페르마 소정리). p가 소수가 아니면 역원이 존재하지 않는 b가 생긴다.
소수가 아니면 생기는 문제
m = 8이고 1 / 2 mod 8, 즉 2x ≡ 1 (mod 8)을 만족하는 x를 구한다고 하자.
- x=0: 2×0 = 0
- x=1: 2×1 = 2
- x=2: 2×2 = 4
- x=3: 2×3 = 6
- x=4: 2×4 = 0 … 이후 반복
2x mod 8의 결과는 {0, 2, 4, 6}만 나온다. 홀수인 1이 절대 나올 수 없으므로 2의 곱셈 역원은 존재하지 않는다. gcd(2, 8) = 2 ≠ 1이기 때문이다.
소수 p에 대해서는 1 ≤ b < p인 모든 b가 p와 서로소이므로 이 문제가 발생하지 않는다.
응용 예시
팩토리얼이나 조합처럼 매우 큰 수를 다룰 때, 곱셈 역원 덕분에 나눗셈을 모듈러 안에서 처리할 수 있다.
C(n, k) = n! × (k!)⁻¹ × ((n-k)!)⁻¹ (mod p)페르마 소정리에 의해 a⁻¹ ≡ a^(p-2) (mod p)이므로, 거듭제곱으로 역원을 구할 수 있다.
MOD = 10**9 + 7
def modinv(a, p=MOD): return pow(a, p - 2, p)
def comb(n, k): if k > n: return 0 num = 1 den = 1 for i in range(k): num = num * (n - i) % MOD den = den * (i + 1) % MOD return num * modinv(den) % MOD왜 10^9+7인가
10^9+7 (1000000007)은 10자리인 첫 번째 소수다. 32비트 정수(약 2.1×10^9)에 들어가면서, 두 수의 곱 (p-1)² < 2^63이므로 64비트 정수로 오버플로우 없이 곱셈 후 모듈러를 취할 수 있다.
참고