1. 모듈로 연산이란?
모듈로 연산이란 한 수를 다른 수로 나눈 나머지를 구하는 연산을 말한다.
기호로는 $\bmod$를 써서 $A\bmod{B} = R$과 같이 나타낸다.
모듈로 연산은 덧셈, 뺄셈, 곱셈에 대해 분배 법칙이 적용된다.
$$ (A \pm B) \bmod{C} = (A \bmod{C} \pm B \bmod{C}) \bmod{C} $$
$$ (A \times B) \bmod{C} = (A \bmod{C} \times B \bmod{C}) \bmod{C} $$
1-1. 모듈로 연산에서의 합동
어떤 두 수 $A$와 $B$를 각각 $C$로 나눈 나머지가 같을 때, 이를 모듈로 합동이라고 한다.
식으로 나타내면 $A = B + K * C\;(K \in \mathbb{Z})$이며, 간단하게 $A \equiv B \pmod{C}$라고 표현한다.
$A \equiv B \pmod{M}$이고 $C \equiv D \pmod{M}$이면 아래와 같은 식들이 성립한다.
$$ A \pm C \equiv B \pm D \pmod{M}$$
$$ A \times C \equiv B \times D \pmod{M}$$
$$ A^{K} \equiv B^{K} \pmod{M},\;C^{K} \equiv D^{K} \pmod{M}$$
2. 최대공약수 구하기 - 유클리드 호제법
최대공약수(Greatest Common Divisor; GCD)를 구하는 가장 널리 알려진 방법은 소인수 분해를 이용하는 방법이다.
하지만 수가 커질수록 소인수 분해에 많은 시간이 걸리게 된다.
유클리드 호제법은 두 수의 최대공약수($gcd(a, b)$)를 보다 빠르게 계산하는 방법이다.
2-1. 유클리드 호제법이란?
유클리드 호제법에 따르면, 두 양의 정수 $a, b\;(a>b)$에 대해 $a \equiv r \pmod{b}$라면 아래와 같은 공식이 성립한다.
$gcd(a, b) = gcd(b, r)$ ($r = 0$이면 $gcd(a, b) = b$)
$a \equiv r \pmod{b}$이므로 $r$에 $a \bmod b$를 대입하면 $gcd(a, b)$의 값을 재귀적으로 구할 수 있다.
예를 들어 28와 16의 경우, $gcd(28, 16) = gcd(16, 12) = gcd(12, 4) = 4$이다.
참고로 GCD값을 활용해 최소공배수(Lowest Common Multiple; LCM)도 쉽게 구할 수 있다.
$$lcm(a, b) = \frac{ab}{gcd(a, b)}$$
2-2. 코드로 구현해보기 (C/C++)
재귀 함수를 이용하면 $O(log_2{(min(a, b))})$ 시간 안에 동작하도록 간단하게 구현할 수 있다.
int gcd(int a, int b) {
if (a % b == 0) return b;
return gcd(b, a % b);
}
2-3. 확장해보기 - 확장 유클리드 호제법
유클리드 호제법을 확장해 아래 식을 만족하는 $x, y$를 구해보자.
$$ax + by = gcd(a, b)$$
먼저 $bx' + (a \bmod b)y' = gcd(b, a \bmod b)$를 만족하는 $x', y'$ 값을 알고 있다고 가정해보자.
위 식에 $a \bmod b = a - \lfloor a/b \rfloor \cdot b$를 대입하면 아래와 같은 식이 된다.
$$ bx' + (a - \lfloor a/b \rfloor \cdot b)y' = gcd(b, a \bmod b) $$
식을 정리하고 $gcd(a, b) = gcd(b, a \bmod b)$를 적용하면 최종적으로 아래 식을 구할 수 있다.
$$ ay' + b(x' - \lfloor a/b \rfloor \cdot y') = gcd(a, b) $$
위 과정을 통해 원래의 식에서 $x = y', y = x' - \lfloor a/b \rfloor \cdot y'$임을 알 수 있다.
이를 바탕으로 $\{x, y, gcd(a, b)\}$를 리턴하는 확장된 GCD 함수를 아래와 같이 작성할 수 있다.
tuple<int, int, int> gcd(int a, int b) {
if (b == 0) return {1, 0, a};
int x, y, g;
tie(x, y, g) = gcd(b, a % b);
return {y, x - (a / b) * y, g};
}
3. 큰 수의 모듈로 연산
3-1. 분할 정복을 이용한 모듈로 연산
어떤 수의 값이 $x^n$ 꼴이라면, 분할 정복을 이용해 $O(log_2{n})$의 시간 안에 모듈로 연산을 수행할 수 있다.
방식은 간단하다.
모듈로 연산의 성질에 따라 $x^n \bmod m = (x^{n/2} \bmod m) \cdot (x^{n/2} \bmod m)$임을 이용하면 된다.
$n$이 홀수라면 $x^n \bmod m = (x^{n-1} \bmod m) \cdot (x \bmod m)$을 이용하면 된다.
int powmod(int x, int n, int m) {
if (n == 0) return 1 % m;
long long value = powmod(x, n/2, m);
value = (value * value) % m;
if (n % 2 == 1) value = (value * x) % m;
return value;
}
3-2. 오일러 정리
1 ~ $n$의 정수 중 $n$과 서로소인 정수의 개수를 나타내는 함수 $\varphi(n)$를 오일러 피 함수라고 한다.
예를 들어, $\varphi(10)$은 $10$과 서로소인 정수의 개수이므로 $\varphi(10)=4$이다. $(1, 3, 7, 9)$
$\varphi(n)$의 값은 $n$을 소인수 분해한 후 공식을 이용해 계산할 수 있다.
어떤 양의 정수 $n$이 $n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}$로 소인수 분해될 때,
$$\varphi(n) = \prod_{i=1}^{k} p_i^{a_i-1} (p_i - 1)$$
오일러 정리란, 모든 서로소인 정수 $x$와 $m$에 대해 아래와 같은 식이 성립한다는 정리이다.
$x^{\varphi(m)} \bmod m = 1$
여기서 $m$이 소수이면 $\varphi(m) = m - 1$이므로 아래와 같은 식이 성립하는데, 이는 페르마의 소정리로 알려져 있다.
$x^{m-1} \bmod m = 1$
페르마의 소정리를 이용하면 $n$이 매우 큰 경우에도 $x^n \bmod m$의 값을 구해낼 수 있다.
$x^n \bmod m = x^{n \bmod (m - 1)} \bmod m$
3-3. 모듈로 곱셈 역원
모듈로 곱셈 역원이란 $x \cdot x^{-1} \bmod m = 1$을 만족시키는 $x^{-1}$ 값을 의미한다. ($inv_m(x)$으로도 표기한다.)
모듈로 곱셈 역원을 이용하면 나눗셈 결과를 $m$으로 나눈 나머지를 구할 수 있다.
$x$로 나누는 것은 $inv_m(x)$를 곱하는 것과 같기 때문이다.
예를 들어, $inv_{17}(6)=3\;(6 \cdot 3 \bmod 17 = 1)$이므로 $24/6 \bmod 17 = 24 \cdot 3 \bmod 17$이다.
모듈로 곱셈 역원은 $x$와 $m$이 서로소일 경우에만 존재한다.
오일러 정리를 적용하면 아래와 같은 식을 구할 수 있다.
$inv_m(x) = x^{\varphi(m)-1}$
$m$이 소수라면 $\varphi(m) = m - 1$이므로 아래와 같은 식이 성립한다.
$inv_m(x) = x^{m-2}$
다시 한 번 $inv_{17}(6)$을 구해보자.
$inv_{17}(6) \bmod 17 = 6^{17 - 2} \bmod 17 = 3$이므로 앞선 결과와 같음을 알 수 있다.
반대로 말하면, $x^n$ 꼴의 모듈러 연산을 역원을 구하는 것으로 빠르게 구할 수 있다는 말이다!
