뤼카의 정리(Lucas' theorem)

2021/02/11 ・

Algorithm

#정수론 #Problem solving

뤼카의 정리는 음이 아닌 정수 $m, n$ 소수 $p$ 에 대해 $(\binom{m}{n}) mod p$ 를 쉽게 구할 수 있게 해주는 정리다.

공식

음이 아닌 정수 $m, n$ 소수 $p$ 에 대해 뤼카의 정리는 다음과 같다.

$(\binom{m}{n}) \equiv \prod_{i = 0}^{k} (\binom{m_{i}}{n_{i}}) (\mod p)$

이때 $m$ 과 $n$ 은 각각 다음과 같다.

$m = m_{k} p^{k} + m_{k - 1} p^{k - 1} + \dots + m_{1} p + m_{0}$

$n = n_{k} p^{k} + n_{k - 1} p^{k - 1} + \dots + n_{1} p + n_{0}$

사용

아주 큰 숫자 $m, n$ 에 대해 이항 계수 $(\binom{m}{n})$ 을 구해야 하나 정확한 값을 알 필요는 없고 적당히 작은 소수 $p$ 로 나눈 나머지만 알면 될 때 사용할 수 있다.

연습문제: 백준 11402

증명

step 1.

$p$ 가 소수이고 $n$ 이 $1 \leq n \leq p - 1$ 인 정수일 때, 이항 계수 $(\binom{p}{n})$ 은 다음과 같다.

$(\binom{p}{n}) = \frac{p \cdot (p - 1) \dots (p - n - 1)}{n \cdot (n - 1) \dots 1}$

이 식의 분모는 $p$ 로 나누어 떨어지지 않고( $∵ n \leq p - 1$ , $p$ 는 소수) 분자는 $p$ 로 나누어 떨어진다. 따라서 $p ∣ (\binom{p}{n})$ 이고 이를 통해 다음 식을 얻을 수 있다.

$(1 + X)^{p} \equiv 1 + X^{p} (\mod p)$

위 식의 양 변에 $p$ 제곱을 하는 귀납법을 통해 모든 음수가 아닌 $i$ 에 대해 다음이 성립한다.

$(1 + X)^{p^{i}} \equiv 1 + X^{p^{i}} (\mod p)$

step 2.

결론부터 말하자면 다음을 보일 것이다.

$\sum_{n = 0}^{m} (\binom{m}{n}) X^{n} \equiv \sum_{n = 0}^{m} (\prod_{i = 0}^{k} (\binom{m_{i}}{n_{i}})) X^{n} (\mod p)$

음수가 아닌 정수 $m$ 과 소수 $p$ 가 있다고 하자. 이때 $m$ 을 다음과 같이 표현할 수 있다.

$m = \sum_{i = 0}^{k} m_{i} p^{i} (0 \leq m_{i} \leq p - 1)$

step 1의 결과를 이용하면

$\begin{aligned} \sum_{n = 0}^{m} (\binom{m}{n}) X^{n} & = (1 + X)^{m} \\ = \prod_{i = 0}^{k} {((1 + X)^{p^{i}})}^{m_{i}} \\ \equiv \prod_{i = 0}^{k} (1 + X^{p^{i}})^{m_{i}} \\ = (1 + X^{p^{0}})^{m_{0}} (1 + X^{p^{1}})^{m_{1}} \dots (1 + X^{p^{k}})^{m_{k}} \end{aligned}$

위 식에서 어떤 $n$ 에 대해 $X^{n}$ 의 계수를 구하고 싶다. 이때 $n$ 역시 다음과 같이 표현할 수 있다.

$n = \sum_{i = 0}^{k} n_{i} p^{i} (0 \leq n_{i} \leq p - 1)$

따라서 $X^{n}$ 를 만들기 위해선 각 $X^{p^{i}}$ 가 $n_{i}$ 번 곱해진 후 전체가 모두 곱해져야 한다.

$(1 + X^{p^{i}})^{m_{i}}$ 에서 $X^{p^{i} n_{i}}$ 의 계수는 $(\binom{m_{i}}{n_{i}})$ 이므로 $X^{n}$ 의 계수는 $\prod_{i = 0}^{k} (\binom{m_{i}}{n_{i}})$ 이다.

그러므로

$\begin{aligned} \prod_{i = 0}^{k} (1 + X^{p^{i}})^{m_{i}} & = (1 + X^{p^{0}})^{m_{0}} (1 + X^{p^{1}})^{m_{1}} \dots (1 + X^{p^{k}})^{m_{k}} \\ = \sum_{n = 0}^{m} (\prod_{i = 0}^{k} (\binom{m_{i}}{n_{i}})) X^{n} \end{aligned}$

정리하면 다음 식을 얻는다.

$\sum_{n = 0}^{m} (\binom{m}{n}) X^{n} \equiv \sum_{n = 0}^{m} (\prod_{i = 0}^{k} (\binom{m_{i}}{n_{i}})) X^{n} (\mod p)$

임의의 $n (1 \leq n \leq m)$ 에 대해 양 변의 $X^{n}$ 의 계수가 합동이므로 결론적으로 우리가 원하는 합동식을 얻을 수 있다.

$∴ (\binom{m}{n}) \equiv \prod_{i = 0}^{k} (\binom{m_{i}}{n_{i}}) (\mod p)$

출처: 위키백과

뤼카의 정리(Lucas' theorem)

공식

사용

증명

step 1.

step 2.

Related content