이항계수 나머지(뤼카 정리) 계산기

n과 k를 소수 p의 진법으로 적었을 때, C(n, k) ≡ Π C(nᵢ, kᵢ) (mod p)라는 정리입니다. 자릿수는 모두 p 미만이라 곱해야 할 이항계수가 아주 작고, 자릿수 개수는 log_p(n)이라 몇 개뿐입니다. C(1000, 500) 같은 300자리 수를 만들지 않고도 나머지를 구할 수 있습니다.

p진법으로 적었을 때 어느 한 자리에서든 k의 숫자가 n의 숫자보다 크면 나누어떨어집니다. 그 자리의 항이 C(작은수, 큰수) = 0이 되어 곱 전체가 0이 되기 때문입니다. 큰 수를 만들지 않고 자릿수만 견주면 되므로 판정이 매우 빠릅니다.

쓸 수 없습니다. 증명이 (1+x)^p ≡ 1 + x^p (mod p)에서 출발하는데, 이 합동식은 C(p, i)가 0 < i < p에서 모두 p로 나누어떨어질 때만 성립하고 그것은 p가 소수일 때뿐입니다. 실제로 C(4, 2) = 6을 4로 나눈 나머지는 2인데 4진법으로 억지로 적용하면 0이 나옵니다. 합성수 법에서는 소인수마다 따로 구해 중국인의 나머지 정리로 합치는 방법(안드레 정리 등)을 씁니다.

p = 2일 때의 뤼카 정리 때문입니다. 2진법에서 각 자리의 이항계수는 C(0,0) = C(1,0) = C(1,1) = 1이고 C(0,1) = 0뿐이므로, C(n, k)가 홀수인 것과 k의 모든 1비트가 n에도 있는 것(k & n = k)이 같아집니다. 이 조건이 자기 닮음 구조를 만들어 홀수 자리를 칠하면 시에르핀스키 삼각형이 됩니다.

n을 2진법으로 적었을 때의 1비트 개수를 b라 하면 정확히 2^b개입니다. 각 비트마다 「k에 넣을지 말지」를 독립으로 고를 수 있기 때문입니다. 그래서 1, 3, 7, 15처럼 비트가 모두 1인 행은 전부 홀수이고, 2, 4, 8처럼 비트가 하나뿐인 행은 양 끝 둘만 홀수입니다.

경진 프로그래밍에서 「C(n, k)를 소수로 나눈 나머지」를 구할 때 표준으로 쓰입니다. n이 매우 크고 p가 작을 때 특히 유용한데, 팩토리얼을 p까지만 전처리해 두면 자릿수마다의 항을 상수 시간에 구할 수 있기 때문입니다. 정수론에서 이항계수의 소인수 분해를 따질 때도 쿠머 정리와 함께 쓰입니다.

p가 n보다 크면 자릿수가 하나뿐이라 뤼카 정리가 아무 도움이 되지 않습니다. 그때는 팩토리얼과 그 역원을 p까지 전처리해 C(n, k) = n!·(k!)⁻¹·((n−k)!)⁻¹로 바로 구하는 편이 낫습니다. 뤼카 정리는 p가 n보다 작아 자릿수가 여럿일 때 이깁니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이루어지고 넣은 값은 이 기기에만 남습니다.