[Algorithm] 뤼카의 정리(Lucas' Theorem)

설명

뤼카의 정리(Lucas' Theorem)는 조합론에서 사용되는 중요한 정리로, 특히 모듈로 $p$ ($p$가 소수일 때)의 이항계수를 계산할 때 유용하다.
 
이 정리는 프랑스의 수학자 에두아르 뤼카(Édouard Lucas)에 의해 발견되었다.

공식

뤼카의 정리의 핵심은 이항계수 $\binom{n}{k}$ (n과 k는 양의 정수, $\binom{n}{k}$는 n 위에 k를 쓴 이항계수를 의미)가 소수 $p$에 대하여 모듈로 $p$로 나눈 나머지를 구할 때,
 
$n$과 $k$를 $p$진법(베이스 p)으로 확장한 후 각 자릿수를 별도로 이항계수 계산에 적용하여 최종 결과를 모듈로 $p$로 얻을 수 있다.  
이를 수학적으로 표현하면, $n$과 $k$를 $p$진법으로 표현했을 때, $(n = n_0 + n_1p + n_2p^2 + \cdots)$ 그리고 $(k = k_0 + k_1p + k_2p^2 + \cdots)$ (여기서 $n_i$와 $k_i$는 $p$진법에서의 자릿수)라고 할 때,

$$ \binom{n}{k} \equiv \binom{n_0}{k_0} \cdot \binom{n_1}{k_1} \cdot \binom{n_2}{k_2} \cdot \cdots \ (\text{mod } p) $$

이 정리는 큰 수의 이항계수를 소수 모듈로 계산할 때, 직접 계산하는 것보다 훨씬 적은 계산으로 결과를 도출할 수 있게 해준다.

예시

$n=10$, $k=3$이고 $p=7$일 때,
 
뤼카의 정리에 의해 구해지는 값은 다음과 같다.
 
10의 7진수 : [1,3]

3의 7진수 : [0,3]
 

$$\binom{10}{3} \text{mod } 7 = \binom{3}{3} \cdot \binom{1}{0} = 1$$