뤼카의 정리

1. 개요

뤼카의 정리는 임의의 음이 아닌 정수 m과 n, 소수 p에 대해 이항 계수의 합동식을 나타내는 정리이다. 이 정리는 이항 계수를 소수 p에 대한 p진 전개를 이용하여 표현하며, 조합적 증명과 생성 함수를 이용한 증명 등 다양한 방법으로 증명될 수 있다. 뤼카의 정리는 이항 계수가 소수 p로 나누어 떨어지는 조건을 제시하며, 쿠머 정리와 q-루카스 정리와 같은 다른 정리와 관련이 있다.

2. 공식화

임의의 음이 아닌 정수 m과 n, 소수 p에 대하여 뤼카의 정리는 다음과 같이 합동식으로 표현할 수 있다.

:$\backslash binom\{m\}\{n\}\backslash equiv\backslash prod\_\{i=0\}^k\backslash binom\{m\_i\}\{n\_i\}\backslash pmod\; p,$

여기서 m과 n을 소수 p에 대해 p진 전개하면 다음과 같다.

:$m=m\_kp^k+m\_\{k-1\}p^\{k-1\}+\backslash cdots\; +m\_1p+m\_0,$
:$n=n\_kp^k+n\_\{k-1\}p^\{k-1\}+\backslash cdots\; +n\_1p+n\_0$

한쪽의 전개가 k에서 끝나지 않더라도 더 이상 전개하지 않고 정리를 적용시키는 것이 가능하다. m < n인 경우 $\backslash tbinom\{m\}\{n\}\; =\; 0$이다.

뤼카의 정리는 임의의 자연수 q에 대해 법 p의 q제곱 형태로 일반화할 수 있다.

3. 증명

뤼카의 정리를 증명하는 데는 여러 방법이 있다. 여기서는 초등적인 이론만을 이용하는 증명을 소개한다. 앞에서와 같이 m, n, p를 택하고, m과 n의 p-진 전개를 위와 같이 쓸 때, 이항 정리에 의해 다음이 성립한다.(x는 정수)

:$(1\; +\; x)^\{p^m\}\; \backslash equiv\; 1\; +\; x^\{p^m\}\; \backslash pmod\; p$

이를 이용해서 다음과 같이 전개하여,

:$\backslash sum\_\{n=0\}^m\; \backslash binom\{m\}\{n\}x^n\; \backslash equiv\; (1+x)^m\; \backslash equiv\; \backslash prod\_\{i=0\}^k\backslash left[(1+x)^\{p^i\}\backslash right]^\{m\_i\}\; \backslash equiv\; \backslash prod\_\{i=0\}^k\backslash left[1+x^\{p^i\}\backslash right]^\{m\_i\}\; \backslash pmod\; p$

다시 이항 정리를 써서 안쪽의 식을 풀어내면,

:$\backslash equiv\; \backslash prod\_\{i=0\}^k\backslash left[\backslash sum\_\{n\_i=0\}^\{m\_i\}\backslash binom\{m\_i\}\{n\_i\}x^\{n\_ip^i\}\backslash right]\; \backslash equiv\; \backslash sum\_\{n=0\}^m\; \backslash left[\backslash prod\_\{i=0\}^k\backslash binom\{m\_i\}\{n\_i\}\backslash right]x^n\; \backslash pmod\; p$

이 된다. 법 p에 대한 형식적 멱급수 전개에서 모든 차수마다의 계수는 같으므로, 원하는 결과를 얻는다.

루카스 정리(Lucas's theorem)를 증명하는 방법에는 여러 가지가 있다.

조합적 증명

M을 m개의 원소를 가진 집합이라고 하고, 다양한 i 값에 대해 길이를 pⁱ로 하는 m_i개의 순환(사이클)으로 나눈다. 그러면 이러한 각 순환은 개별적으로 회전될 수 있으므로, 순환군(cyclic group) C_pⁱ의 데카르트 곱인 군 G가 M에 작용한다. 따라서 크기가 n인 부분 집합 N에도 작용한다. G의 원소 개수는 p의 거듭제곱이므로, 그 궤도(orbit)도 마찬가지이다. 따라서 $\backslash tbinom\{m\}\{n\}$을 모듈로(modulo) p로 계산하려면 이 군 작용의 고정점(fixed point)만 고려하면 된다. 고정점은 몇몇 순환의 합집합인 부분 집합 N이다. 보다 정확하게는 k-i에 대한 귀납법에 의해, N은 크기가 pⁱ인 정확히 n_i개의 순환을 가져야 함을 보일 수 있다. 따라서 N에 대한 선택의 수는 정확히 $\backslash prod\_\{i=0\}^k\backslash binom\{m\_i\}\{n\_i\}\backslash pmod\{p\}$이다.

생성 함수를 이용한 증명

뤼카의 정리를 증명하는 방법 중 하나는 생성 함수를 이용하는 것이다. 이 증명은 네이선 파인(Nathan Fine)에 의한 것이다.

먼저, p가 소수이고 n이 1 ≤ n ≤ p − 1인 정수일 때, 이항 계수 $\backslash binom\{p\}\{n\}$의 분자는 p로 나누어지지만 분모는 그렇지 않다. 따라서 p는 $\backslash binom\{p\}\{n\}$을 나눈다. 이는 일반 생성 함수(ordinary generating functions)의 관점에서 보면, $(1+X)^p\backslash equiv1+X^p\backslash pmod\{p\}$임을 의미한다. 귀납법을 통해, 모든 음이 아닌 정수 i에 대해 $(1+X)^\{p^i\}\backslash equiv1+X^\{p^i\}\backslash pmod\{p\}$가 성립한다.

이제 m을 음이 아닌 정수, p를 소수라고 하고, m을 p진법으로 $m=\backslash sum\_\{i=0\}^\{k\}m\_ip^i$와 같이 표현한다. 여기서 k와 m_i는 음이 아닌 정수이고, 0 ≤ m_i ≤ p-1이다. 그러면,

:$\backslash begin\{align\}$
\sum_{n=0}^{m}\binom{m}{n}X^n &
=(1+X)^m=\prod_{i=0}^{k}\left((1+X)^{p^i}\right)^{m_i}\\
& \equiv \prod_{i=0}^{k}\left(1+X^{p^i}\right)^{m_i}
=\prod_{i=0}^{k}\left(\sum_{j_i=0}^{m_i}\binom{m_i}{j_i}X^{j_ip^i}\right)\\
& =\prod_{i=0}^{k}\left(\sum_{j_i=0}^{p-1}\binom{m_i}{j_i}X^{j_ip^i}\right) \\
& =\sum_{n=0}^{m}\left(\prod_{i=0}^{k}\binom{m_i}{n_i}\right)X^n
\pmod{p},
\end{align}

가 성립한다. 여기서 n을 p진법으로 나타내는 것은 유일하며, 최종 곱에서 n_i는 n의 p진법 표현에서 i번째 숫자이다. 따라서 뤼카의 정리가 증명된다.

3.1. 조합적 증명

M을 m개의 원소를 가진 집합이라고 하고, 다양한 i 값에 대해 길이를 pⁱ로 하는 m_i개의 순환(사이클)으로 나눈다. 그러면 이러한 각 순환은 개별적으로 회전될 수 있으므로, 순환군(cyclic group) C_pⁱ의 데카르트 곱인 군 G가 M에 작용한다. 따라서 크기가 n인 부분 집합 N에도 작용한다. G의 원소 개수는 p의 거듭제곱이므로, 그 궤도(orbit)도 마찬가지이다. 따라서 $\backslash tbinom\{m\}\{n\}$을 모듈로(modulo) p로 계산하려면 이 군 작용의 고정점(fixed point)만 고려하면 된다. 고정점은 몇몇 순환의 합집합인 부분 집합 N이다. 보다 정확하게는 k-i에 대한 귀납법에 의해, N은 크기가 pⁱ인 정확히 n_i개의 순환을 가져야 함을 보일 수 있다. 따라서 N에 대한 선택의 수는 정확히 $\backslash prod\_\{i=0\}^k\backslash binom\{m\_i\}\{n\_i\}\backslash pmod\{p\}$이다.

3.2. 생성 함수를 이용한 증명

뤼카의 정리를 증명하는 방법 중 하나는 생성 함수를 이용하는 것이다. 이 증명은 네이선 파인(Nathan Fine)에 의한 것이다.

먼저, p가 소수이고 n이 1 ≤ n ≤ p − 1인 정수일 때, 이항 계수 $\backslash binom\{p\}\{n\}$의 분자는 p로 나누어지지만 분모는 그렇지 않다. 따라서 p는 $\backslash binom\{p\}\{n\}$을 나눈다. 이는 일반 생성 함수(ordinary generating functions)의 관점에서 보면, $(1+X)^p\backslash equiv1+X^p\backslash pmod\{p\}$임을 의미한다. 귀납법을 통해, 모든 음이 아닌 정수 i에 대해 $(1+X)^\{p^i\}\backslash equiv1+X^\{p^i\}\backslash pmod\{p\}$가 성립한다.

이제 m을 음이 아닌 정수, p를 소수라고 하고, m을 p진법으로 $m=\backslash sum\_\{i=0\}^\{k\}m\_ip^i$와 같이 표현한다. 여기서 k와 m_i는 음이 아닌 정수이고, 0 ≤ m_i ≤ p-1이다. 그러면,

:$\backslash begin\{align\}$
\sum_{n=0}^{m}\binom{m}{n}X^n &
=(1+X)^m=\prod_{i=0}^{k}\left((1+X)^{p^i}\right)^{m_i}\\
& \equiv \prod_{i=0}^{k}\left(1+X^{p^i}\right)^{m_i}
=\prod_{i=0}^{k}\left(\sum_{j_i=0}^{m_i}\binom{m_i}{j_i}X^{j_ip^i}\right)\\
& =\prod_{i=0}^{k}\left(\sum_{j_i=0}^{p-1}\binom{m_i}{j_i}X^{j_ip^i}\right) \\
& =\sum_{n=0}^{m}\left(\prod_{i=0}^{k}\binom{m_i}{n_i}\right)X^n
\pmod{p},
\end{align}

가 성립한다. 여기서 n을 p진법으로 나타내는 것은 유일하며, 최종 곱에서 n_i는 n의 p진법 표현에서 i번째 숫자이다. 따라서 뤼카의 정리가 증명된다.

4. 결과

이항 계수 $\backslash tbinom\{m\}\{n\}$은 n의 p진수 자리수 중 적어도 하나가 m의 해당 자리수보다 클 경우에만 소수 p로 나누어 떨어진다. 특히, $\backslash tbinom\{m\}\{n\}$은 n의 이진법 전개에서 이진수 (비트)가 m의 비트의 부분 집합일 경우에만 홀수이다.

5. 일반화

뤼카의 정리는 을 소수 거듭제곱 p^k으로 나눈 나머지를 나타내는 표현으로 일반화될 수 있다. 하지만 공식은 더 복잡해진다.

만약 모듈로가 소수 p의 제곱이라면, 모든 0 ≤ s ≤ r ≤ p − 1, a ≥ 0, 그리고 b ≥ 0에 대해 다음 합동 관계가 성립한다.
:
여기서 은 n번째 조화수이다.

더 높은 소수 거듭제곱 p^k에 대한 뤼카 정리의 일반화는 데이비스와 웹(1990)와 그랜빌(1997)에 의해서도 제시되었다.

쿠머 정리는 소수 p^k가 이항 계수 $\backslash tbinom\{m\}\{n\}$를 나누는 가장 큰 정수 k(즉, 소수 p에 대한 이항 계수의 p 진수 값)는 n과 m − n을 위치 기수법 p를 사용하여 더할 때 발생하는 올림의 수와 같다고 주장한다.

q-루카스 정리는 J. 데자르메니앙에 의해 처음 증명된, q-이항 계수에 대한 일반화이다.

5.1. 소수가 아닌 법

뤼카의 정리는 을 소수 거듭제곱 p^k으로 나눈 나머지를 나타내는 표현으로 일반화될 수 있다. 하지만 공식은 더 복잡해진다.

만약 모듈로가 소수 p의 제곱이라면, 모든 0 ≤ s ≤ r ≤ p − 1, a ≥ 0, 그리고 b ≥ 0에 대해 다음 합동 관계가 성립한다.

:

여기서 은 n번째 조화수이다.

더 높은 소수 거듭제곱 p^k에 대한 뤼카 정리의 일반화는 데이비스와 웹(1990)와 그랜빌(1997)에 의해서도 제시되었다.

5.1.1. 법 p² 합동 관계

뤼카의 정리는 $\backslash tbinom\; mn$을 소수 거듭제곱 p^k으로 나눈 나머지를 나타내는 표현으로 일반화될 수 있다. 하지만 공식은 더 복잡해진다.

만약 모듈로가 소수 p의 제곱이라면, 모든 0 ≤ s ≤ r ≤ p − 1, a ≥ 0, 그리고 b ≥ 0에 대해 다음 합동 관계가 성립한다.
:$\backslash binom\{pa+r\}\{pb+s\}\backslash equiv\backslash binom\; ab\backslash binom\; rs(1+pa(H\_r-H\_\{r-s\})+pb(H\_\{r-s\}-H\_s))\backslash pmod\{p^2\},$
여기서 $H\_n=1+\backslash tfrac12+\backslash tfrac13+\backslash cdots+\backslash tfrac1n$은 n번째 조화수이다.

더 높은 소수 거듭제곱 p^k에 대한 뤼카 정리의 일반화는 데이비스와 웹(1990)와 그랜빌(1997)에 의해서도 제시되었다.

5.1.2. 더 높은 소수 거듭제곱

뤼카의 정리는 $\backslash tbinom\; mn$을 소수 거듭제곱 p^k으로 나눈 나머지를 나타내는 표현으로 일반화될 수 있다. 하지만 공식은 더 복잡해진다.

만약 모듈로가 소수 p의 제곱이라면, 모든 0 ≤ s ≤ r ≤ p − 1, a ≥ 0, 그리고 b ≥ 0에 대해 다음 합동 관계가 성립한다.
:$\backslash binom\{pa+r\}\{pb+s\}\backslash equiv\backslash binom\; ab\backslash binom\; rs(1+pa(H\_r-H\_\{r-s\})+pb(H\_\{r-s\}-H\_s))\backslash pmod\{p^2\},$
여기서 $H\_n=1+\backslash tfrac12+\backslash tfrac13+\backslash cdots+\backslash tfrac1n$은 n번째 조화수이다.

더 높은 소수 거듭제곱 p^k에 대한 뤼카 정리의 일반화는 데이비스와 웹(1990)와 그랜빌(1997)에 의해서도 제시되었다.

6. 다른 정리와의 관계

쿠머 정리는 소수 p^k가 이항 계수 $\backslash tbinom\{m\}\{n\}$를 나누는 가장 큰 정수 k(즉, 소수 p에 대한 이항 계수의 p 진수 값)는 n과 m − n을 위치 기수법 p를 사용하여 더할 때 발생하는 올림의 수와 같다고 주장한다.

q-루카스 정리는 J. 데자르메니앙에 의해 처음 증명된, q-이항 계수에 대한 일반화이다.