뤼카의 정리

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

공식화

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

• $(\genfrac{}{}{0ex}{}{m}{n})\equiv \prod _{i=0}^k(\genfrac{}{}{0ex}{}{m_i}{n_i})(\mathrm{mod}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}(\mathrm{mod}p)$

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

$\sum _{n=0}^m(\genfrac{}{}{0ex}{}{m}{n})x^n\equiv (1+x{)}^m\equiv \prod _{i=0}^k{[(1+x{)}^{p^i}]}^{m_i}\equiv \prod _{i=0}^k{[1+x^{p^i}]}^{m_i}(\mathrm{mod}p)$

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

$\equiv \prod _{i=0}^k\left[\sum _{n_i=0}^{m_i}(\genfrac{}{}{0ex}{}{m_i}{n_i})x^{n_i{p}^i}\right]\equiv \sum _{n=0}^m\left[\prod _{i=0}^k(\genfrac{}{}{0ex}{}{m_i}{n_i})\right]x^n(\mathrm{mod}p)$

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

외부 링크

• 플래닛매스 - 뤼카의 정리 틀:웹아카이브