모듈러 연산 정리 (p. 513)
1. 모듈러 덧셈 / 뺄셈 / 곱셈#
모듈러 연산에서 덧셈, 뺄셈, 곱셈은 다음 성질을 가진다.
$$ (x+y)\%M = ((x\%M)+(y\%M))\%M $$$$ (x-y)\%M = ((x\%M)-(y\%M) + M)\%M $$$$ xy\%M = (\;(x\%M)\cdot (y\%M)\;)\%M $$즉,
전체에 대해 mod를 하든 각각 mod를 한 뒤 계산하든 결과는 같다.
2. 모듈러 나눗셈은 왜 안 될까?#
나눗셈은 다르다. 아래 식은 성립하지 않는다.
$$ (y/x)\%M = ((y\%M)\;/\;(x\%M))\%M $$왜냐하면 mod 세계에서는 일반적인 의미의 분수 $\frac{1}{x}$이 항상 존재하지 않기 때문이다.
3. 그렇다면 모듈러에서 나눗셈은 어떻게 할까?#
모듈러에서의 나눗셈은 "역원을 곱하는 것" 으로 정의된다.
3-1. 모듈러 곱셈 역원(Modular Multiplicative Inverse)#
$$ xy \equiv 1 \pmod{M} $$을 만족하는 정수 $y$를
mod M에서 x의 모듈러 곱셈 역원
이라고 한다. 보통 아래와 같이 $x^{-1}$로 표기한다.
$$ x \cdot x^{-1} \equiv 1 \pmod{M} $$3-2. 모듈러 곱셈 역원은 언제 존재할까?#
$$ gcd(x,M)=1 $$일 때만 존재한다.
3-3. 그래서 나눗셈은 모듈러 곱셈 역원으로 바꿔 계산한다.#
$$ \frac{a}{x} $$를
$$ a \cdot x^{-1} $$로 바꿔 계산한다.
4. 소수 mod에서 모듈러 곱셈 역원 구하기#
M이 소수이고 $x \not \equiv 0 \pmod M$이면, 페르마 소정리에 의해
$$ x^{M-1} \equiv 1 \pmod{M} $$이 성립한다. 이를 지수로 분해하면
$$ x^{M-2}\cdot x \equiv 1 \pmod{M} $$이 된다. 이 식은 정확히
$$ x \cdot (어떤 수) \equiv 1 \pmod{M} $$형태이므로,
$$ x^{M-2} $$는 mod M에서 x의 모듈러 곱셈 역원이다. 즉,
5. 그래서 모듈러 나눗셈은 이렇게 계산한다#
$$ (y/x)\%M = y\cdot x^{M-2}\%M $$그리고 곱셈의 모듈러 성질에 의해
$$ = ((y\%M)\cdot (x\%M)^{M-2})\%M $$6. PS에서 모듈러 곱셈 역원은 언제 쓰이는가?#
“이항계수를 소수 M으로 모듈러한 결과를 구할 때 쓴다.”
PS에서는 보통 큰 수가 나오면 $\pmod M$을 하여 답을 출력하도록 하는 경우가 많은데, 이 때 이항계수( $nCr$ ) 를 $\pmod M$해야 하는 경우 분모의 팩토리얼 연산 값이 너무 커져 그 값을 다 구한 다음 $\pmod M$ 연산하기가 매우 힘들 때도 있다. 이 때 모듈러 곱셈 역원(Modular Multiplicative Inverse)을 쓰게 되면, 값이 64비트 정수 크기를 벗어나기 전에 $\pmod M$을 할 수 있어 계산이 가능해진다.
6-1. 이항계수%M을 모듈러 곱셈 역원 사용방식으로 변경#
$$ nCr = \frac{n!}{r!(n-r)!} $$$\pmod M$에서는
$$ nCr\%M = \frac{n!}{r!(n-r)!}\%M $$$$ = \frac{n!}{(n-r)!}\cdot (r!)^{-1} \pmod M $$$$ = (r!)^{-1} \cdot \prod_{i=n-r+1}^{n}i \pmod M $$그리고
$$ (r!)^{-1} \equiv (r!)^{M-2} \pmod M $$이므로
$$ \therefore nCr\%M \;=\; (r!)^{M-2} \cdot \prod_{i=n-r+1}^{n}i \pmod M $$6-2. 위의 식 코드로 구현하기#
이는 코드로 아래와 같이 구현할 수 있다.
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
const int M = 1e9+7;
int Pow(int x, int n) {
if(n==0) return 1;
ll ret = Pow(x, n/2);
ret *= ret;
ret %= M;
if(n%2==0) return ret;
else return ret*x%M;
}
int main() {
int n,r,M=1e9+7;
cin >> n >> r;
ll ifact=1, rfact=1;
for(int i=1, j=n; i<=r; i++, j--) {
ifact *= j;
ifact %= M;
rfact *= i;
rfact %= M;
}
//calculate nCr % M
printf("%lld\n", (ll)Pow(rfact, M-2) * ifact % M);
return 0;
}위 코드는 BOJ 11401(boj.kr/11401)의 AC 코드이기도 하다.
7. 페르마 소정리 증명#
7-1. 페르마 소정리 (Fermat’s Little Theorem)#
M이 소수이고 $gcd(b,M)\text{=}1$이면
$$ b^{M-1} \equiv 1 \pmod M $$
7-2. 증명#
7-2-1. 집합 $S$ 정의#
다음과 같은 집합이 있다고 하자.
$$ S = \{1,2,3, ..., M\text{-}1\} $$M이 소수이므로 이 집합의 모든 원소는 M과 서로소이다.
7-2-2. 각 원소에 $b$를 곱한 집합 $bS$#
집합 S의 모든 원소에 b를 곱한 집합을 생각하자.
$$ bS = \{b\cdot1,b\cdot2,b\cdot3, ..., b\cdot(M\text{-}1)\} $$이제 이 원소들을 mod M으로 본다.
7-2-3. $S \equiv bS\pmod M$ 임을 보이기#
만약
$$ bi \equiv bj\pmod M \quad(i,j \in S) $$이라면,
$$ b(i-j) \equiv 0 \pmod M $$이다.
$M$은 소수이고 $gcd(b,M)\text{=}1$이므로 $b$는 $\pmod M$에서 역원이 존재한다.
따라서 양변을 b로 약분할 수 있고,
$$ i \equiv j \pmod M $$이 된다.
그런데 $i,j \in S$ 이므로 결국
$$ i=j $$이다.
즉,
서로 다른 i에 대해 bi mod M은 모두 서로 다르다.
따라서
$$ bS \equiv S \pmod M $$즉, b를 곱해도 집합은 단지 순열(permutation)만 될 뿐이다.
7-2-4. 집합 전체 곱 비교#
각 집합의 모든 원소 곱을 $P, P'$이라 하자. 이를 식으로 나타내면 아래와 같다.
$$ P = \prod_{i=1}^{M-1}i\;,\quad P' = b^{M-1}\prod_{i=1}^{M-1}i $$즉,
$$ P' = b^{M-1}P $$그런데 증명 3)에서 보았듯이 $S \equiv bS \pmod M$이므로
이다. 따라서
$$ P \equiv b^{M-1}P \pmod M $$7-2-5. 약분#
M은 소수이고 $P = \prod_{i=1}^{M-1}i$ 이므로 P는 M의 배수가 아니다.
즉,
$$ gcd(P,M)=1 $$따라서 $\pmod M$에서 P는 역원이 존재하므로 양변을 P로 약분할 수 있다.
$$ b^{M-1} \equiv 1 \pmod M $$증명 완료