이항계수와 모듈러 연산의 깊은 이해: BOJ 11401을 통해 얻은 통찰

백준 온라인 저지 11401번 문제("이항계수 3")를 해결하며, 차근차근 풀어가는 과정을 공유하고자 합니다.

학습 주제

• 오늘 공부한 주제: 이항계수와 모듈러 연산, 페르마 소정리, 모듈러 역원, 군론
• 대화 제목: 이항계수와 조합
• 학습 날짜: 2026년 2월 1일

질문과 탐구

처음에는 "이항계수 = 조합"이라는 당연한 사실에서 출발했습니다. 하지만 BOJ 11401번 문제, 특히 4,000,000까지 확장되는 $n$과 $k$를 다뤄야 하는 상황에 직면하면서, 단순 조합 공식으로는 해결할 수 없다는 것을 깨달았습니다. "모듈러 연산에서 나눗셈은 어떻게 처리해야 하는가?" 라는 근본적인 궁금증이 생겼고, 이 궁금증이 페르마 소정리와 모듈러 역원의 세계로 파고들었습니다.

주요 질문들은 다음과 같습니다.

• 모듈러 연산에서 나눗셈은 어떻게 정의되는가?
• 페르마 소정리는 무엇이며, 어떻게 모듈러 역원을 구하는 데 사용되는가?
• $a^{p-2}\equiv a^{-1}(\mathrm{mod}p)$ 는 어떻게 유도되는가?
• modpow 함수에서 b & 1과 a = a * a는 각각 어떤 수학적 의미를 가지는가?
• Z_p^*는 무엇이며, 왜 페르마 소정리를 적용하려면 이 집합의 원소여야 하는가?
• 라그랑주 정리와 원소의 차수(order)는 페르마 소정리와 어떤 관계가 있는가?

핵심 학습 내용

1. 이항계수와 모듈러 연산의 만남

이항계수는 $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\frac{n!}{k!(n-k)!}$ 로 정의됩니다. 모듈러 $p$ 환경에서 이 공식을 그대로 적용하면 문제가 발생하는데, 바로 모듈러 연산에서는 나눗셈이 직접적으로 정의되지 않기 때문입니다.

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

이 식은 모듈러 $p$에서 직접 계산할 수 없습니다. 이를 해결하기 위해 우리는 분수를 분자 곱하기 분모의 역원으로 변환해야 합니다.

$$\left(\genfrac{}{}{0ex}{}{n}{k}\right)\equiv n!\cdot (k!(n-k)!{)}^{-1}(\mathrm{mod}p)$$

2. 모듈러 역원과 페르마 소정리

모듈러 $p$에서 어떤 수 $a$의 역원 $a^{-1}$은 $a\cdot a^{-1}\equiv 1(\mathrm{mod}p)$ 를 만족하는 수입니다. $p$가 소수이고 $a\not\equiv 0(\mathrm{mod}p)$ (즉, $a$가 $p$의 배수가 아닐 때)라는 조건 하에, 페르마 소정리가 등장합니다.

페르마 소정리는 다음과 같습니다.
$$a^{p-1}\equiv 1(\mathrm{mod}p)$$

이 식의 양변에 $a^{-1}$을 곱하면 놀라운 결과를 얻게 됩니다.
$$a^{p-1}\cdot a^{-1}\equiv 1\cdot a^{-1}(\mathrm{mod}p)$$
$$a^{p-2}\equiv a^{-1}(\mathrm{mod}p)$$

결론적으로, 모듈러 $p$에서 $a$의 역원은 $a^{p-2}(\mathrm{mod}p)$ 로 계산할 수 있게 됩니다. 이 발견이 BOJ 11401번 문제 해결의 핵심 열쇠가 되었습니다.

3. $a\in {\mathbb{Z}}_p^{\ast }$ 와 군론

페르마 소정리가 성립하려면 $a$는 $p$와 서로소여야 하며, 즉 $a\not\equiv 0(\mathrm{mod}p)$ 여야 합니다. $p$가 소수일 때, $\{1,2,\dots ,p-1\}$ 집합, 즉 ${\mathbb{Z}}_p^{\ast }$ 는 곱셈에 대해 닫혀 있고 모든 원소가 역원을 가지므로 **곱셈군(multiplicative group)**을 이룹니다.

이 군론적 관점에서 '원소의 차수(order)'라는 개념이 중요해집니다. 어떤 원소 $a$의 차수 $\text{ord}(a)$는 $a^k\equiv 1(\mathrm{mod}p)$ 를 만족하는 가장 작은 양의 정수 $k$를 의미합니다. 라그랑주 정리에 따르면, 유한군 $G$의 모든 원소 $a$에 대해 $\text{ord}(a)$는 $|G|$ (군의 크기)의 약수입니다.

${\mathbb{Z}}_p^{\ast }$ 의 크기는 $p-1$이므로, 모든 $a\in {\mathbb{Z}}_p^{\ast }$ 에 대해 $\text{ord}(a)$는 $p-1$의 약수입니다. 따라서 $a^{p-1}=(a^{\text{ord}(a)}{)}^m=1^m=1$ 이 되어 페르마 소정리가 자연스럽게 성립하게 됩니다.

4. 빠른 거듭제곱 (Binary Exponentiation)

$p-2$는 최대 $10^9+7-2$ 정도로 매우 큰 수입니다. $a^{p-2}$를 직접 $p-2$번 곱하는 것은 시간 초과를 유발합니다. 여기서 '빠른 거듭제곱' 알고리즘이 사용됩니다.

이 알고리즘은 지수 $b$를 이진수로 표현하여 $O(\log b)$ 시간에 $a^b(\mathrm{mod}p)$를 계산합니다. 핵심 아이디어는 다음과 같습니다.

• $b$를 이진수로 분해: $b=\sum bi{t}_i\cdot 2^i$
• $a^b=\prod a^{(bi{t}_i\cdot 2^i)}$
• 코드에서는 a = a * a를 통해 $a^{2^i}$를 순차적으로 만들고, b & 1 (최하위 비트 검사)로 현재 비트가 1인지 확인하여 res에 곱합니다.

long long modpow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1) { // b의 최하위 비트가 1이면
            res = res * a % MOD; // 현재 a^(2^i) 항을 결과에 누적
        }
        a = a * a % MOD; // 다음 비트를 위해 a를 제곱 (a^(2^i) -> a^(2^(i+1)))
        b >>= 1;         // b를 오른쪽으로 시프트 (다음 비트로 이동)
    }
    return res;
}

핵심 학습 내용 요약

• 이항계수 mod p: $\left(\genfrac{}{}{0ex}{}{n}{k}\right)\equiv n!\cdot (k!(n-k)!{)}^{p-2}(\mathrm{mod}p)$
• 모듈러 역원: $a^{-1}\equiv a^{p-2}(\mathrm{mod}p)$ (페르마 소정리 활용)
• 필수 조건: $p$는 소수, $a\in {\mathbb{Z}}_p^{\ast }$ (즉, $a\not\equiv 0(\mathrm{mod}p)$)
• 계산: 팩토리얼은 O(n) 전처리, 역원은 $O(\log p)$ 빠른 거듭제곱 사용.

이해한 내용

이번 학습을 통해 저는 다음과 같은 점들을 새롭게 알게 되거나 명확히 이해하게 되었습니다.

• 모듈러 연산에서의 나눗셈: 단순한 뺄셈이 아니라 '역원과의 곱셈'으로 대체된다는 것을 명확히 알게 되었습니다.
• 페르마 소정리의 실용성: 단순히 수학 공식으로만 알았던 것을, 모듈러 역원을 구하는 강력한 도구로 인식하게 되었습니다. $a^{p-2}$가 $a^{-1}$이 되는 과정이 단순한 '트릭'이 아니라 군론적 구조에서 필연적으로 나온다는 것을 이해했습니다.
• 환 사상(Ring Homomorphism): 모듈러 연산($\mathrm{mod}p$)이 덧셈과 곱셈의 구조를 그대로 보존하는 환 사상이라는 것을 알게 되었습니다. 이 성질 덕분에 중간중간 $\mathrm{mod}p$를 적용해도 결과가 달라지지 않는다는 것을 확신하게 되었습니다.
• 군론의 중요성: ${\mathbb{Z}}_p^{\ast }$ 가 곱셈군을 이룬다는 사실, 라그랑주 정리, 원소의 차수(order)가 어떻게 페르마 소정리와 연결되는지를 수학적, 구조적으로 이해하게 되었습니다.
• 빠른 거듭제곱의 원리: 지수를 이진수로 분해하고, 밑을 제곱해나가면서 필요한 항만 곱하는 방식이 어떻게 $O(\log b)$의 효율을 내는지 코드와 수학식을 연결하여 명확히 이해했습니다. a = a * a 가 단순히 밑을 바꾸는 것이 아니라 a_0^{2^i} 로 진화하는 과정임을 파악했습니다.

특히 $a\in {\mathbb{Z}}_p^{\ast }$ 여야 하는 이유, $p$가 소수여야만 하는 이유, 그리고 $a$의 $p-1$ 승이 1이 되는 과정에서 라그랑주 정리가 어떻게 핵심적인 근거가 되는지 깊이 이해할 수 있었습니다.

실전 적용

이번 학습 내용은 앞으로 다양한 모듈러 연산이 필요한 알고리즘 문제에서 핵심적으로 활용될 것입니다.

• 이항계수 문제: $\left(\genfrac{}{}{0ex}{}{n}{k}\right)(\mathrm{mod}p)$ 를 풀어야 하는 문제 (BOJ 1010, 11050 등) 에 바로 적용할 수 있습니다.
• 확률 및 기대값: 모듈러 연산을 사용하는 확률, 기대값 문제에서도 분수 계산이 필요할 때 역원을 활용할 수 있습니다.
• DP 문제: DP 테이블에 모듈러 값을 저장해야 할 때, 덧셈, 곱셈뿐만 아니라 나눗셈이 필요한 경우에도 이 지식을 활용할 수 있습니다.

실습 계획:

1. BOJ 1010번 (이항계수 1)과 BOJ 11050번 (이항계수 2)을 풀어보며 기본적인 모듈러 역원 활용을 익힙니다.
2. 모듈러 역원을 직접 구현하는 modInverse 함수를 만들고, modpow와 연동하여 다양한 문제에 적용해봅니다.
3. 이항계수 외에 모듈러 역원이 필요한 다른 유형의 문제들을 찾아 풀어봅니다.

응용 아이디어:

• 큰 $n$ 값에 대한 피보나치 수열의 모듈러 값을 계산할 때, 행렬 거듭제곱과 함께 모듈러 역원을 활용하는 방법을 탐구해 볼 수 있습니다.
• 암호학에서 사용되는 모듈러 연산(RSA 등)과 페르마 소정리의 관계를 더 깊이 파고들어볼 수 있습니다.

추가 학습 계획

이번 학습을 통해 추상대수학의 개념들이 실제 알고리즘 문제 풀이에 얼마나 강력하게 적용되는지 느꼈습니다. 앞으로 다음과 같은 부분을 더 깊이 공부하고 싶습니다.

• 군론 심화: 순환군, 생성자(generator), 원시근(primitive root)의 개념을 더 깊이 이해하고, 이산 로그 문제(Discrete Logarithm Problem)와의 연관성을 탐구하고 싶습니다.
• 유한체(Finite Field): ${\mathbb{Z}}_p$ 가 체(field)가 되는 조건과 그 성질을 더 깊이 학습하여, 유한체 위에서의 다항식 연산 등 알고리즘에 적용될 수 있는 부분을 찾아보고 싶습니다.
• 다양한 모듈러 역원 계산 방법: 확장 유클리드 호제법 등 페르마 소정리 외의 모듈러 역원 계산 방법을 알아보고, 각 방법의 장단점을 비교 분석하고 싶습니다.

관련 자료로는 "Abstract Algebra"와 같은 군론/환론 교재, 그리고 "Introduction to Algorithms"와 같은 알고리즘 서적의 모듈러 산술 파트를 참고할 계획입니다.

참고 자료

이번 학습에서 ChatGPT가 매우 유용하게 활용되었습니다. 특히 다음과 같은 자료들을 추천받았습니다.

• 페르마 소정리: Wikipedia, Wolfram MathWorld 등
• 모듈러 역원: 다양한 온라인 코딩 강의 및 알고리즘 튜토리얼
• 군론 기초: Wikipedia의 "Group (mathematics)", "Lagrange's theorem" 항목
• 빠른 거듭제곱 알고리즘: 알고리즘 관련 서적 및 온라인 자료

이번 학습은 단순한 문제 해결을 넘어, 컴퓨터 과학과 수학이 어떻게 깊이 연결되어 있는지를 보여주는 소중한 경험이었습니다. 앞으로도 이러한 깊이 있는 학습을 꾸준히 이어가고 싶습니다.