뤼카의 정리

뤼카의 정리(Lucas' theorem, -定理)는 수론과 조합론에서 이용되는 정리로, 프랑스인 수학자 에두아르 뤼카(Édouard Lucas)의 이름이 붙어 있다. 이 정리는 어떤 조합의 수를 소수 p에 대해 법 p 상에서 구할 때 간편한 계산 방식을 제공한다. 에두아르 뤼카가 처음 이 정리를 발표한 것은 1878년 논문에서였다.

공식화

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

• ${\binom {m}{n}}\equiv \prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}{\pmod {p}},$

여기서 첨자가 붙은 수들은 m과 n을 소수 p에 대해 다음과 같이 p진 전개했을 때 얻어지는 것이다. 덧붙여, 한쪽의 전개가 k에서 끝나지 않더라도 더 이상 전개하지 않고 정리를 적용시키는 것이 가능하다.

1. $m=m_{k}p^{k}+m_{k-1}p^{k-1}+\cdots +m_{1}p+m_{0},$
2. $n=n_{k}p^{k}+n_{k-1}p^{k-1}+\cdots +n_{1}p+n_{0}$

이상과 같은 뤼카의 정리는 임의의 자연수 q에 대해 법 p의 q제곱 형태로 일반화할 수 있다. 그 자세한 형태는 이 문단에 달린 주석의 논문을 참조.

증명

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

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

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

$\sum _{n=0}^{m}{\binom {m}{n}}x^{n}\equiv (1+x)^{m}\equiv \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}}{\pmod {p}}$

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

$\equiv \prod _{i=0}^{k}\left[\sum _{n_{i}=0}^{m_{i}}{\binom {m_{i}}{n_{i}}}x^{n_{i}p^{i}}\right]\equiv \sum _{n=0}^{m}\left[\prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}\right]x^{n}{\pmod {p}}$

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

외부 링크

• 플래닛매스 - 뤼카의 정리 Archived 2007년 9월 30일 - 웨이백 머신