뤼카 정리 (이항계수)

자릿수에 따라 나누기

n과 k를 p진법으로 쓰고 짧은 쪽의 앞에는 0을 보충해 자리를 맞춘다. 각 자리에서 위 숫자 nᵢ와 아래 숫자 kᵢ의 이항계수를 계산하고 모두 곱한다. 이 곱과 원래 이항계수는 p로 나눈 나머지가 같다. 원래 정수 값이 그대로 같다는 의미는 아니다.

작은 예의 계산

p=3에서 14는 112₍₃₎이고 4는 011₍₃₎이다. 따라서 binom(14,4)는 binom(1,0)binom(1,1)binom(2,1)=2와 3을 법으로 합동이다. 실제 binom(14,4)=1001이며 이를 3으로 나눈 나머지도 2다.

나누어떨어지는 조건

어느 자리에서 kᵢ>nᵢ이면 해당 이항계수는 0이므로 전체 이항계수가 p의 배수다. 예를 들어 6=020₍₃₎이므로 binom(14,6)에서는 가운데 자리의 binom(1,2)가 0이다. 반대로 모든 자리에서 kᵢ≤nᵢ이면 자리 숫자들이 p보다 작아 각 인수는 p의 배수가 아니므로 전체도 p로 나누어떨어지지 않는다.

소수 조건과 적용 범위

이 정리는 소수 p를 법으로 사용한다. 합성수나 소수의 제곱을 법으로 바꿔 같은 자리별 공식을 그대로 적용해서는 안 된다. 큰 n과 k의 이항계수를 직접 만드는 대신 작은 자릿수 문제들로 나누는 데 의미가 있으며, 계산 결과는 나머지임을 유지해야 한다.