모듈러 산술 (Modular Arithmetic)

modular-arithmetic, Modular Arithmetic, 모듈러 산술, 합동 관계, modular exponentiation, modular inverse, modular multiplication, mod 연산

정의

모듈러 산술 (Modular Arithmetic) 은 정수를 특정 수 $m$ 으로 나눈 나머지 로 대응시켜 다루는 산술 체계입니다.

합동 관계 $a\equiv b(\mathrm{mod}\{)m\}$: $a$ 와 $b$ 를 $m$ 으로 나눈 나머지가 같음.

$$a\equiv b(\mathrm{mod}\{)m\}⟺m\mid (a-b)$$

예: $17\equiv 5(\mathrm{mod}12)$ (17시 = 오후 5시)

응용:

• 정수론
• 암호학 (RSA, ECDSA)
• 해싱 (해시 함수)
• 알고리즘 (경쟁 프로그래밍 mod 답)

왜 필요한가

• 큰 수 관리: n! 등이 int64 초과 시 mod $10^9+7$
• 순환 구조: 시계, 요일
• 역원 존재 (mod 소수): 나눗셈을 곱셈으로

기본 연산

$a\equiv a^{\prime }(\mathrm{mod}\{)m\}$, $b\equiv b^{\prime }(\mathrm{mod}\{)m\}$ 이면:

$$a+b\equiv a^{\prime }+b^{\prime }(\mathrm{mod}\{)m\}$$ $$a-b\equiv a^{\prime }-b^{\prime }(\mathrm{mod}\{)m\}$$ $$a\cdot b\equiv a^{\prime }\cdot b^{\prime }(\mathrm{mod}\{)m\}$$

나눗셈은 특수 (아래 modular inverse 참조).

코드

const long long MOD = 1e9 + 7;

long long addm(long long a, long long b) { return (a + b) % MOD; }
long long subm(long long a, long long b) { return ((a - b) % MOD + MOD) % MOD; }
long long mulm(long long a, long long b) { return (a * b) % MOD; }

주의: 뺄셈 시 음수 방지 위해 + MOD 후 % MOD.

Modular Exponentiation (거듭제곱)

$a^n\mathrm{mod}m$ 을 $O(\log n)$ 에.

Fast exponentiation (분할 정복):

a^n = \begin\{cases\} 1 & n = 0 \\ (a^\{n/2\})^2 & n \text\{ even\} \\ a \cdot a^\{n-1\} & n \text\{ odd\} \end\{cases\}

long long powm(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

시간: $O(\log n)$.

Modular Inverse (역원)

$a\cdot a^{-1}\equiv 1(\mathrm{mod}\{)m\}$ 을 만족하는 $a^{-1}$.

존재 조건: $\gcd (a,m)=1$ (서로소).

모듈러 나눗셈:

$$\frac{\{}{a}\}\{b\}\mathrm{mod}m=a\cdot b^{-1}\mathrm{mod}m$$

방법 1: 페르마 소정리 (mod 가 소수)

$m$ 이 소수이면:

$$a^{-1}\equiv a^{\{}m-2\}(\mathrm{mod}\{)m\}$$

이유: 페르마 소정리 $a^{\{}m-1\}\equiv 1(\mathrm{mod}m)$ → $a\cdot a^{\{}m-2\}\equiv 1$.

long long inv(long long a, long long m) {
    return powm(a, m - 2, m);   // mod 가 소수일 때만
}

가장 흔한 방법 (경쟁 프로그래밍 MOD = 10^9 + 7 은 소수).

방법 2: 확장 유클리드

$\gcd (a,m)=1$ 이면 임의의 $m$ 에.

$$ax+my=1⟹a\cdot x\equiv 1(\mathrm{mod}m)$$

long long extGcd(long long a, long long b, long long& x, long long& y) {
    if (b == 0) { x = 1; y = 0; return a; }
    long long x1, y1;
    long long g = extGcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

long long inv(long long a, long long m) {
    long long x, y;
    extGcd(a, m, x, y);
    return (x % m + m) % m;
}

자주 쓰는 문제

1. $\left(\genfrac{}{}{0ex}{}{\{}{n}\right)\}\{k\}\mathrm{mod}p$ (이항 계수)

큰 $n$ 에 대해:

$$\left(\genfrac{}{}{0ex}{}{\{}{n}\right)\}\{k\}=\frac{\{}{n}!\}\{k!\cdot (n-k)!\}$$

팩토리얼 미리 계산 + 역원:

const int MAXN = 1e6;
long long fact[MAXN + 1], invFact[MAXN + 1];

void precompute() {
    fact[0] = 1;
    for (int i = 1; i <= MAXN; i++) fact[i] = fact[i-1] * i % MOD;
    invFact[MAXN] = powm(fact[MAXN], MOD - 2, MOD);
    for (int i = MAXN - 1; i >= 0; i--) invFact[i] = invFact[i+1] * (i+1) % MOD;
}

long long binom(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * invFact[k] % MOD * invFact[n-k] % MOD;
}

2. 등비수열 합

$1+r+r^2+\dots +r^{\{}n-1\}={\frac{\{}{r}}^n-1\}\{r-1\}$

mod 로 계산 시 $\frac{1}{\{}r-1\}$ 을 역원으로.

Chinese Remainder Theorem (CRT)

여러 mod 조건을 만족하는 해:

\begin\{cases\} x \equiv a_1 \pmod\{m_1\} \\ x \equiv a_2 \pmod\{m_2\} \\ \vdots \end\{cases\}

$m_i$ 가 서로소이면 유일한 해 (mod $\prod m_i$) 존재. 자세한 것은 CRT 참조.

응용: 큰 mod 를 작은 mod 여러 개로 분할 (병렬 계산).

페르마 소정리 vs 오일러 정리

페르마: $p$ 소수, $\gcd (a,p)=1$ 이면 $a^{\{}p-1\}\equiv 1(\mathrm{mod}p)$.

오일러 확장: 임의 $m$, $\gcd (a,m)=1$ 이면 $a^{\{}\varphi (m)\}\equiv 1(\mathrm{mod}m)$.

• $\varphi (m)$: 오일러 phi 함수 (자세한 것은 Euler Phi 참조)

Modular Multiplication 오버플로

long long 곱셈은 $2^{63}$ 넘을 수 있음:

• $a,b\text{<}10^9$: a * b < 10^{18} < 2^{63} OK
• $a,b\text{<}10^{18}$: 오버플로

해결책:

1. __int128 (GCC):

   long long mulm(long long a, long long b, long long m) {
       return (__int128)a * b % m;
   }

2. Barrett reduction, Montgomery multiplication (고급)
3. 두 배 분할:

   long long mulm(long long a, long long b, long long m) {
       long long result = 0;
       a %= m;
       while (b > 0) {
           if (b & 1) result = (result + a) % m;
           a = (a * 2) % m;
           b >>= 1;
       }
       return result;
   }

흔한 MOD

• 10^9 + 7: 소수, int32 곱 시 오버플로 안 남. 대회 표준.
• 10^9 + 9: 대안 소수
• 998244353: NTT (Number Theoretic Transform) 친화 소수 ($119\cdot 2^{23}+1$)
• 2^61 - 1: 큰 소수 (해싱)

함정

관련 위키

• 유클리드 호제법
• 확장 유클리드
• 오일러 Phi 함수
• 페르마 소정리
• 중국인 나머지 정리
• 조합론
• 파스칼 삼각형
• 이산수학