뤼카의 정리

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

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

공식화[편집]

임의의 음이 아닌 정수 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_kp^k+m_{k-1}p^{k-1}+\cdots +m_1p+m_0,
  2. n=n_kp^k+n_{k-1}p^{k-1}+\cdots +n_1p+n_0

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

증명[편집]

뤼카의 정리를 증명하는 데는 여러 방법이 있다. 여기서는 초등적인 이론만을 이용하는 증명을 소개한다. 앞에서와 같이 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[(1+x)^{p_i}]^{m_i} \equiv \prod_{i=0}^k[1+x^{p_i}]^{m_i} \pmod p

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

\equiv \prod_{i=0}^k[\sum_{n_i=0}^{m_i}\binom{m_i}{n_i}x^{n_ip^i}] \equiv \sum_{n=0}^m [\prod_{i=0}^k\binom{m_i}{n_i}]x^n \pmod p

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

주석[편집]

  1. Andrew Granville (1997년). Arithmetic Properties of Binomial Coefficients I: Binomial coefficients modulo prime powers. 《Canadian Mathematical Society Conference Proceedings》 20: 253–275. MR1483922.

바깥 고리[편집]