뤼카의 정리

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. 조합적 증명

3. 2. 생성 함수를 이용한 증명

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''번째 조화수이다.^[3]

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

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

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

5. 1. 소수가 아닌 법

5. 1. 1. 법 p² 합동 관계

5. 1. 2. 더 높은 소수 거듭제곱

6. 다른 정리와의 관계

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

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

참조

_[1] 논문 Théorie des Fonctions Numériques Simplement Périodiques
_[2] 논문 Binomial coefficients modulo a prime
_[3] arXiv Lucas' theorem modulo p2 2020-06-21
_[4] 논문 Lucas' Theorem for Prime Powers
_[5] 논문 Arithmetic Properties of Binomial Coefficients I: Binomial coefficients modulo prime powers http://www.dms.umont[...]
_[6] 논문 Un Analogue des Congruences de Kummer pour les q-nombres d'Euler 1982-03
_[7] 논문 Théorie des Fonctions Numériques Simplement Périodiques
_[8] 논문 Arithmetic Properties of Binomial Coefficients I: Binomial coefficients modulo prime powers http://www.dms.umont[...] 2016-09-30