뤼카의 정리

(뤼카의정리에서 넘어옴)

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

공식화

편집

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

  •  

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

  1.  
  2.  

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

증명

편집

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

 

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

 

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

 

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

각주

편집
  1. Andrew Granville (1997). “Arithmetic Properties of Binomial Coefficients I: Binomial coefficients modulo prime powers” (PDF). 《Canadian Mathematical Society Conference Proceedings》 20: 253–275. MR 1483922. 2017년 2월 2일에 원본 문서 (PDF)에서 보존된 문서. 2016년 9월 30일에 확인함. 

외부 링크

편집