[Algo] 뤼카의 정리

Park Yeongseo·2023년 4월 6일

Algorithm

목록 보기

3/17

뤼카 정리는 어떤 조합 $\binom{N}{K}$ 를 소수 $p$ 로 나눈 나머지를 구하고자 할 때 사용할 수 있다. 그 정리는 다음과 같다.

자연수 $N$ , 음이 아닌 정수 $K$ , 소수 $p$ 가 주어졌을 때,
$\binom{N}{K} \equiv\prod_{i=0}^{K}{\binom{m_i}{n_i}}\pmod{p}$

여기서 $m_i$ 와 $n_i$ 는 각각 $N$ 과 $K$ 를 $p$ 진법으로 전개해 나타냈을 때의 각 자리의 수들이다.
즉 다음과 같다.

N = m_kp^k + m_{k-1}p^{k-1} + ... + m_2p^2 + m_1p^1+ m_0p^0\\ K = n_kp^k + n_{k-1}p^{k-1} + ... + n_2p^2 + n_1p^1+ n_0p^0

뤼카의 정리를 증명하기 전에 우선 다음의 항등식을 떠올려보자.

(x+1)^n = \binom{n}{n}x^n + \binom{n}{n-1}x^{n-1} + ... + \binom{n}{2}x^2 + \binom{n}{1}x + \binom{n}{0}

이 항등식의 $n$ 에 $p^r(p$ 는 소수, $r$ 은 음이 아닌 정수 $)$ 을 대입한다면 다음처럼 될 것이다.

(x+1)^{p^r} = \binom{p^r}{p^r}x^{p^r} + \binom{p^r}{p^r-1}x^{p^r-1} + ... + \binom{p^r}{2}x^2 + \binom{p^r}{1}x + \binom{p^r}{0}

그런데 위 항등식에서 볼 수 있는 것은

\binom{p^r}{p^r-1}, \binom{p^r}{p^r-2}, ..., \binom{p^r}{2}, \binom{p^r}{1}

가 모두 $p$ 의 배수라는 것이다. 따라서 다음과 같이 표기할 수 있다.

p \mid \binom{p^r}{p^r-1}x^{p^r-1} + ... + \binom{p^r}{2}x^2 + \binom{p^r}{1}x\\ \iff p \mid (x+1)^{p^r} - (\binom{p^r}{p^r}x^{p^r} + \binom{p^r}{0})\\

당연히 $\binom{p^r}{p^r} = \binom{p^r}{0} = 1$ 이므로 위는 다음과 같이 정리된다.

(x+1)^{p^r} \equiv x^{p^r} + 1 \pmod p

다시 말해 $(x+1)^{p^r}$ 을 $p$ 로 나눈 나머지는 $x^{p^r} + 1$ 을 $p$ 로 나눈 나머지와 같다는 것이다.

여기에서 다음의 정리

a \equiv b \pmod p \Rightarrow a^n \equiv b^n \pmod p

를 사용하면, 우리는 여기에서 $(x+1)^{p^r} \equiv x^{p^r} + 1 \pmod p$ 임을 알고 있으므로,

(x+1)^{p^i} \equiv x^{p^i} + 1 \pmod p \\ \Rightarrow ((x+1)^{p^i})^{m_i} \equiv (x^{p^i} + 1)^{m_i} \pmod p

임을 알 수 있고, 곱에 대한 나머지 정리

a \equiv b \pmod p ,c \equiv d \pmod p \Rightarrow ac \equiv bd \pmod p

를 이용하면

\prod_{i=0}^{k}((x+1)^{p^i})^{m^i} \equiv \prod_{i=0}^{k}(x^{p^i} +1)^{m_i}\pmod p

임도 알 수 있다.

$(x^{p^i} +1)^{m_i}$ 에 다시 이항정리를 사용하면

(x^{p^i} +1)^{m_i} = \binom{m_i}{m_i}x^{p^im^i} + \binom{m_i}{m_i-1}x^{p^i(m_i-1)}+...+\binom{m_i}{1}x^{p^i} + \binom{m_i}{0}

를 얻을 수 있다.
즉

\prod_{i=0}^{k}(x^{p^i} +1)^{m_i} = \prod_{i=0}^{k}\sum_{n_i = 0}^{m_i}\binom{m_i}{n_i}x^{n_ip^i}

이다.
합의 곱은 곱의 합과 같으므로

\sum_{i\in A}i \times \sum_{j\in B} j = \sum_{i \in A j \in B}i\times j

앞의 곱 또한 다음과 같이 합으로 나타낼 수 있다.

\prod_{i=0}^{k}\sum_{n_i = 0}^{m_i}\binom{m_i}{n_i}x^{n_ip^i} = \sum_{n=0}^N\prod_{i=0}^k\binom{m_i}{n_ i}x^{n_ip^i}

따라서 다음처럼 정리 된다.

(1+x)^N \equiv (1+x)^{m_kp^k + m_{k-1}p^{k-1} + ... + m_2p^2 + m_1p^1+ m_0p^0}\\ \equiv \prod_{i=0}^{k}((x+1)^{p^i})^{m^i} \equiv \prod_{i=0}^{k}(x^{p^i} +1)^{m_i}\equiv \sum_{n=0}^N\prod_{i=0}^k\binom{m_i}{n_i}x^{n_ip^i} \pmod p

(1+x)^N = \sum_{n=0}^N\binom{N}{n}x^{n} \equiv \sum_{n=0}^N\prod_{i=0}^k\binom{m_i}{n_i}x^{n} \pmod p

각 $x^n$ 의 계수 또한 $p$ 에 대해 합동이므로 임의의 $K$ 에 대해서도 다음이 성립한다.

\binom{N}{K} \equiv \prod_{i=0}^K\binom{m_i}{n_i} \pmod p

여기서 각 $m_i, n_i$ 가 $N,K$ 를 $p$ 진법으로 나타냈을 때의 자리의 수임을 활용하면 증명 완료. $\square$