2. 뤼카의 정리 - 증명편
뤼카의 정리는 정수론에서 그렇게 필수적인 정리는 아니다. 정수론뿐이 아니라 조합론에도 어느 정도 발을 걸치고 있기 때문.
에두아르 뤼카가 1878년 발표한 논문에서 처음 사용되었는데. 아주 큰 숫자들로 이루어진 이항계수를 상대적으로 매우 작은 소수로 나눠야 할 때 유용하게 사용된다.
당장 11402번 문제에서도 대놓고 사용되었으며, 그게 아니더라도 BOJ에는 몇 가지의 뤼카의 정리 관련한 문제가 있다.
하지만 정리만 알고 증명을 하지 않고 넘어감은 조금 슬픈 일. 직접 증명을 한 단계 한 단계 해 보도록 하자.
증명을 하기 전에, 먼저 정리의 모양새를 보고 들어가자.
$$\binom{M}{N}\equiv\prod_{i=0}^k \binom{m_i}{n_i}\pmod{p}\,\,\,\left(M=\sum_{i=0}^k m_i p^i,N=\sum_{i=0}^k n_i p^i\right)$$
Part I - \(\forall 0<s\in\mathbb{N},(1+x)^{p^s}\equiv 1+x^{p^s}\pmod{p}\) 보이기
우선, 0 < r < p인 소수 p와 자연수 r에 대해서 \(\binom{p}{r}\)이 어떤 모양새를 하고 있는지 확인을 해야 한다.
$$\binom{p}{r}=\frac{p\cdot(p-1)\cdots(p-r+2)\cdot(p-r+1)}{r\cdot(r-1)\cdots2\cdot1}$$
여기서 분자는 p의 배수이지만, 분모는 p보다 작은 수들의 곱이기 때문에 절대로 p의 배수가 될 수 없다. 그렇기 때문에 \(\binom{p}{r}\)은 항상 p의 배수이다.
이제 Part I에서 증명할 명제를 한 번 보자.
s=1인 케이스에선, \( (1+x)^p=\sum_{i=0}^p\binom{p}{i}x^i\equiv\binom{p}{0}x^0+\binom{p}{p}x^p=1+x^p\pmod{p} \)이기 때문에 명제가 성립한다.
이제 s=n인 케이스에서 명제가 성립한다고 가정하자.
그러면 우선 s=1 케이스에 의해서 \((1+x)^{p^{n+1}}=\left((1+x)^p\right)^{p^n}\equiv\left(1+x^p\right)^{p^n}\pmod{p}\)이 된다.
또한 s=n 케이스에 의해서 \(\left(1+x^p\right)^{p^n}\equiv1+\left(x^p\right)^{p^n}=1+x^{p^{n+1}}\pmod{p}\)이 성립하므로, 주어진 명제는 s=n+1일 때도 성립을 하게 된다.
따라서, 수학적 귀납법에 의해서 Part I의 명제는 참이 된다.
Part II - 뤼카의 정리 증명하기
이제 이것만 있으면 바로 뤼카의 정리를 증명할 수 있다! 먼저 가정은 문제에 제시된 것과 똑같이 했다고 하자.
그렇게 된다면 \((1+x)^M=(1+x)^{\sum_{i=0}^km_ip^i}=\prod_{i=0}^{k}\left((1+x)^{p^i}\right)^{m_i}\equiv\prod_{i=0}^{k}\left(1+x^{p^i}\right)^{m_i}\)\(=\left(1+x^1\right)^{m_0}\left(1+x^{p}\right)^{m_1}\cdots\left(1+x^{p^k}\right)^{m_k}\pmod{p}\)이 성립하게 된다.
여기서 \(x^N\)항, 즉 지수가 \(\sum_{i=0}^kn_ip^i\)인 항은 \(x^{p^i}\)를 \{n_i}번 곱해야 나타난다.
그러한 경우의 수는? 오로지 \(\left(1+x^{p^i}\right)^{m_i}\)에서만 얻을 수 있으므로, \(m_i<n_i\)면 0이고, \(m_i\ge n_i\)이면 \(\binom{m_i}{n_i}\)가지가 된다.
따라서, 총 경우의 수는 \(\prod_{i=0}^k \binom{m_i}{n_i}\)가지가 되고, 이는 \((1+x)^M\)의 \(x^N\)항의 계수인 \(\binom{M}{N}\)과 mod p로 같다.
따라서, \(\binom{M}{N}\equiv\prod_{i=0}^k \binom{m_i}{n_i}\pmod{p}\)가 성립힌다. 곧, 뤼카의 정리가 성립하게 된다. ■
어떤가? 증명과정이 완전히 별세계의 소리만은 아니었을 것이다.
modulo라는, 현재 교과 외 방식을 사용하지는 않았으나, 반대로 말하자면 그 외에는 모두 교과 과정의 내용을 소재로 하였다.
이 증명을 이해했다면, 11402번 문제를 자기만의 코드로 다시 풀어보는 것은 어떨까?이번에는 수학적 배경까지 완벽하게 알고 있으니, 전보다는 쉬울 것이다.
